Construct Binary Tree from Preorder and Inorder Traversal(根据前序中序构建二叉树)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

根据前序中序构建二叉树。

1
/ \
2 3
/ \ / \
4 5 6 7对于上图的树来说，
index: 0 1 2 3 4 5 6
先序遍历为: 2 4 5 3 6 7
中序遍历为: 4 2 5 6 3 7
为了清晰表示，我给节点上了颜色，红色是根节点，蓝色为左子树，绿色为右子树。
可以发现的规律是：
1. 先序遍历的从左数第一个为整棵树的根节点。
2. 中序遍历中根节点是左子树右子树的分割点。再看这个树的左子树：
先序遍历为: 2 4 5
中序遍历为: 4 2 5
依然可以套用上面发现的规律。右子树：
先序遍历为: 3 6 7
中序遍历为: 6 3 7
也是可以套用上面的规律的。所以这道题可以用递归的方法解决。
具体解决方法是：
通过先序遍历找到第一个点作为根节点，在中序遍历中找到根节点并记录index。
因为中序遍历中根节点左边为左子树，所以可以记录左子树的长度并在先序遍历中依据这个长度找到左子树的区间，用同样方法可以找到右子树的区间。
递归的建立好左子树和右子树就好。

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null&&inorder==null||(preorder.length==0&&inorder.length==0)) return null;
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public TreeNode build(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){
if(preStart>preEnd||inStart>inEnd) return null; //这里两个下标都要判断
TreeNode root=new TreeNode(preorder[preStart]);
int i;
for(i=inStart;i<=inEnd;i++){ //中序中找到根的位置
if(inorder[i]==preorder[preStart]) break;
} root.left=build(preorder,preStart+1,preStart+i-inStart,inorder,inStart,i-1);
root.right=build(preorder,preStart+i-inStart+1,preEnd,inorder,i+1,inEnd);
return root;
}
}