105. 从前序与中序遍历序列构造二叉树

题目描述

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

输入输出

1
2
3
4
5
6
7
8
9
10
11
           3
          / \
         9  20
           /  \
          15   7

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

输入: preorder = [-1], inorder = [-1]
输出: [-1]

基本思路

递归实现 先用一个Map保存先序遍历各节点的值和index 然后递归实现

java实现

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
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int m = preorder.length;
        int n = inorder.length;
        if(m == 0 || n == 0 || m != n) return null;
        Map<Integer, Integer> map = new HashMap<>(n);
        for(int i = 0; i < n; i++){
            map.put(inorder[i], i);
        }
        return constructTree(preorder, 0, n-1, map, 0, n-1);
    }

    public TreeNode constructTree(int[] pre, int startPre, int endPre,
        Map<Integer, Integer> map, int startIn, int endIn){
            if(startPre > endPre || startIn > endIn){
                return null;
            }
            int rootval = pre[startPre];
            TreeNode root = new TreeNode(rootval);
            int rootindex = map.get(rootval);
            root.left = constructTree(pre, startPre+1, rootindex-startIn+startPre, map, startIn, rootindex-1);
            root.right = constructTree(pre, rootindex-startIn+startPre+1, endPre, map, rootindex+1, endIn);
            return root;
        }
}