GuilinDev

Lc0105

05 August 2008

105 Construct Binary Tree from Preorder and Inorder Traversal

原题概述

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

题意和分析

这道题用先序和中序来建立二叉树，先序的顺序第一个肯定是root，所以二叉树的根结点可以确定，由于题目中说了没有相同的元素，所以利用先序的根我们可以找到这个根在中序的位置，并且在中序的数组中根结点为中心拆分成左右两部分，然后又用我们熟悉的递归调用就可以重建二叉树了。

问题解释

Preorder Traversal: [root, left, right]

Inorder Traversal: [left, root, right]

关键点

  1. preorder的第一个元素总是根节点

  2. 在inorder中找到根节点的位置，左边是左子树，右边是右子树

解题步骤

  1. 从preorder中取出第一个元素作为根节点

  2. 在inorder中找到根节点的位置，左边是左子树，右边是右子树

  3. 递归构建左子树和右子树

代码

递归办法，时空复杂度均为O(n)

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 给inorder遍历中的每个value的index建立索引，方便查询
    private Map<Integer, Integer> inorderIndexMap;
    // index用来遍历preorder array
    private int preorderIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderIndexMap = new HashMap<>();

        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }

        // 从preorder中的第一个元素开始，递归开始build tree
        preorderIndex = 0;
        return buildTreeRecursive(preorder, 0, inorder.length - 1);
    }

    private TreeNode buildTreeRecursive(int[] preorder, int left, int right) {
        // 没有元素可以build tree了
        if (left > right) {
            return null;
        }

        // pick the current element from preorder as the root - 递归过程中preorder中第一个元素总是root
        int rootValue = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootValue);

        // 在inorder中找到当前root的index，方便为左右子树分配元素
        int inorderIndex = inorderIndexMap.get(rootValue);

        //递归构建左右子树
        root.left = buildTreeRecursive(preorder, left, inorderIndex - 1);
        root.right = buildTreeRecursive(preorder, inorderIndex + 1, right);

        return root;
    }
}

迭代办法

  • 我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点；
  • 我们依次枚举前序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向右移动 index，并将当前节点作为最后一个弹出的节点的右儿子；如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的左儿子；
  • 无论是哪一种情况，我们最后都将当前的节点入栈。
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

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}
This site is open source. Improve this page.