leetcode solution 105 Construct Binary Tree from Preorder and Inorder Traversal
z
 2018-03-07 15:49:42  

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

1
2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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) return null;
        if(preorder.length != inorder.length) 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 cur = -1;
        for(int i=inStart; i<=inEnd; i++){
            if(inorder[i] == root.val){
                cur = i;
                break;
            }
        }
        
        root.left = build(preorder, preStart+1, preStart+cur-inStart, inorder, inStart, cur-1);
        root.right = build(preorder, preStart+cur-inStart+1, preEnd, inorder, cur+1, inEnd);
        return root;
    }
}
  • 注意递归时两个数组的start 和 end的位置