Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

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

Posted on In , ,
Symbols count in article: 2.2k Reading time ≈ 2 mins.

来源Leetcode第105题从前序与中序遍历构造二叉树

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

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

例如，给出

1
2
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

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
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
首先根据 preorder 找到根节点是 3
    
然后根据根节点将 inorder 分成左子树和右子树
左子树
inorder [9]

右子树
inorder [15,20,7]

把相应的前序遍历的数组也加进来
左子树
preorder[9] 
inorder [9]

右子树
preorder[20 15 7] 
inorder [15,20,7]

现在我们只需要构造左子树和右子树即可，成功把大问题化成了小问题
然后重复上边的步骤继续划分，直到 preorder 和 inorder 都为空，返回 null 即可

用一个Map存储中序遍历每一个节点的位置，由此确定对应的左右子树范围。

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

private TreeNode helper(int p_start,int p_end,int i_start,int i_end){
    if(p_start == p_end)
        return null;
    TreeNode root = new TreeNode(this.preorder[p_start]);  //构造根节点
    int i_root_index = this.map.get(this.preorder[p_start]);  //得到中序遍历根节点的位置
    int left = i_root_index - i_start;  //这一块为根节点的左子树
    root.left = helper(p_start + 1 , p_start + left + 1,i_start,i_root_index);
    root.right = helper(p_start + 1 + left,p_end,i_root_index + 1 , i_end);
    return root;
}

迭代 栈

来源题解

我们用一个栈保存已经遍历过的节点，遍历前序遍历的数组，一直作为当前根节点的左子树，直到当前节点和中序遍历的数组的节点相等了，那么我们正序遍历中序遍历的数组，倒着遍历已经遍历过的根节点（用栈的 pop 实现），找到最后一次相等的位置，把它作为该节点的右子树。

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
public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) {
        return null;
    }
    Stack<TreeNode> roots = new Stack<TreeNode>();
    int pre = 0;
    int in = 0;
    //先序遍历第一个值作为根节点
    TreeNode curRoot = new TreeNode(preorder[pre]);
    TreeNode root = curRoot;
    roots.push(curRoot);
    pre++;
    //遍历前序遍历的数组
    while (pre < preorder.length) {
        //出现了当前节点的值和中序遍历数组的值相等，寻找是谁的右子树
        if (curRoot.val == inorder[in]) {
            //每次进行出栈，实现倒着遍历
            while (!roots.isEmpty() && roots.peek().val == inorder[in]) {
                curRoot = roots.peek();
                roots.pop();
                in++;
            }
            //设为当前的右孩子
            curRoot.right = new TreeNode(preorder[pre]);
            //更新 curRoot
            curRoot = curRoot.right;
            roots.push(curRoot);
            pre++;
        } else {
            //否则的话就一直作为左子树
            curRoot.left = new TreeNode(preorder[pre]);
            curRoot = curRoot.left;
            roots.push(curRoot);
            pre++;
        }
    }
    return root;
}