105. 从前序与中序遍历序列构造二叉树/面试题07. 重建二叉树(较难)

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

思路1：

前序遍历第一个节点是根节点，中序遍历根据前序遍历的根节点，可以知道左节点，和右节点，递归来就行

思路2

思路一存在一个问题，在中序遍历找到根节点的位置每次都得遍历中序遍历的数组去寻找，我们可以用一个hashmap把中序遍历数组的每个元素的值和下标存起来，这样就可以直接找到了，减少循环

回看记录200622

先序的一个数为根节点，再从中序中找到根节点下标，然后递归调用左右

代码1：

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
/**
 * 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) {
        return BTreeConstruct(preorder, 0,preorder.length-1, inorder,0,inorder.length-1);
    }
    public TreeNode BTreeConstruct(int[] preorder,int ps,int pe, int[] inorder,int is,int ie) {
        if(ps>pe)//头尾一样，所有数据为0，直接返回
            return null;
        //先序头节点就是根
        int rootval = preorder[ps];
        TreeNode root = new TreeNode(rootval);
        //在中序遍历中找到根节点的位置
        int irootindex = 0;
        for(int i=is;i<=ie;i++){
            if(rootval==inorder[i]){
                irootindex = i;
                break;
            }
        }
        int leftNodeNum = irootindex-is;//在中序遍历中根节点左边的节点数
        //递归构造
        root.left = BTreeConstruct(preorder,ps+1,ps+leftNodeNum,inorder,is,irootindex-1);
        root.right = BTreeConstruct(preorder,ps+leftNodeNum+1,pe,inorder,irootindex+1,ie);
        return root;
    }
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public TreeNode buildTree(int[] preorder, int[] inorder) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length, map);
}

private TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end, HashMap<Integer, Integer> map) {
    if (p_start == p_end) {
        return null;
    }
    int root_val = preorder[p_start];
    TreeNode root = new TreeNode(root_val);
    int i_root_index = map.get(root_val);
    int leftNum = i_root_index - i_start;
    root.left = buildTreeHelper(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index, map);
    root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end, map);
    return root;
}

作者：windliang
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--22/