buildTree.png

题目分析

  1. 前序遍历的特点是preorder[0]是根节点
  2. 中序遍历的特点是跟节点左边是左子树，跟节点右边是右子树
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
34
35
36
37
38
39
public class Test {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        int len = preorder.length;
        if (len == 0) {
            return null;
        }

        int rootVal = preorder[0];
        int rootIndex = 0;
        for (int i = 0; i < len; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
            }
        }

        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, rootIndex + 1),
                Arrays.copyOfRange(inorder, 0, rootIndex));

        root.right = buildTree(Arrays.copyOfRange(preorder, rootIndex+1, len),
                Arrays.copyOfRange(inorder, rootIndex+1, len));


        return root;

    }


    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};

        Test test = new Test();
        TreeNode root = test.buildTree(preorder, inorder);

    }
}

python版本更好理解

1
2
3
4
5
6
7
8
9
class Solution:
    def buildTree(self, preorder , inorder):
        if not preorder:
            return None
        loc = inorder.index(preorder[0]) # 在中序遍历中查询当前层的根节点
        root = TreeNode(preorder[0])
        root.left = self.buildTree(preorder[1 : loc + 1], inorder[ : loc])  # 每次都是去掉头节点所以从1开始
        root.right = self.buildTree(preorder[loc + 1 : ], inorder[loc + 1: ])
        return root