本文主要是介绍LeetCode - construct-binary-tree-from-inorder-and-postorder-traversal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
题意：
给你一个二叉树的中序序列和后序序列，确定二叉树。
里面的结点不重复
解题思路：
由后序序列确定根节点
在中序序列中找到根节点，将其左右分为左右子树
递归连接左右子树，最终构造二叉树
代码:
public TreeNode buildTree(int[] inorder, int[] postorder) {if(inorder.length <= 0 || postorder.length <= 0) {return null;}return getTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);}public TreeNode getTree(int[] inorder, int ins, int ine, int[] postorder, int posts, int poste) {if(ins > ine || posts > poste) {return null;}//从后序遍历获取根节点,也就是后序遍历的最后一个结点TreeNode root = new TreeNode(postorder[poste]);//根据根节点在中序遍历中将其分开为左右子树for(int i = ins ;i <= ine ; i++) {if(inorder[i] == postorder[poste]) {root.left = getTree(inorder,ins,i-1,postorder,posts,posts+i-ins-1);root.right = getTree(inorder,i+1,ine,postorder,posts+i-ins,poste-1);}}return root;}
这里面难点在于左右子树的范围难以确定，我现在给出一个具体例子来解释左右子树范围确定
ins 是中序序列inorder的起始位置，ine是终点
posts是后序序列postorder的起始位置，poste是终点
中序序列：ABCDEFG
后序序列：BDCAFGE
根据后序序列 确定E是树的根节点
在中序序列找到E的位置，所以左子树为ABCD，右子树为FG
此时后序序列也把其分为左右子树，左子树为BDCA，右子树为FGE
先递归左子树：
root.left = getTree(inorder,ins,i-1,postorder,posts,posts+i-ins-1);
先看看中序序列的左子树：
ins刚开始index为0，i也就是E的index为4，i-1=3也就是D的index ，所以遍历的范围就是（ABCD）
后序序列的左子树：
posts index为0 ，posts+i-ins-1, i-ins是代表中序序列中根节点的左子树长度，也就是4-0=4 ，posts+i-ins-1为0+4-1=3，也就是A的位置，这里遍历的范围是（BDCA）
递归右子树:
root.right = getTree(inorder,i+1,ine,postorder,posts+i-ins,poste-1);
中序序列的右子树：
i+1,也就是4+1=5，F的位置，ine为inorder.length-1=6，刚好在G的位置，所以右子树遍历就是在(FG)里面
后序序列的左子树：
起始点为posts+i-ins 也就是 0+4-0 =4 ，也就是F的位置， 终点为poste-1 = 6-1=5也就是G的位置，这里减1是因为E已经作为根节点移出去了，所以它的右子树只有（FG）
第一步就是这样的，后面就可以通过递归来不断完善这颗二叉树，所以后面就没写出来了。希望能帮助大家理解这里递归参数的意思。
这篇关于LeetCode - construct-binary-tree-from-inorder-and-postorder-traversal的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
