LeetCode 105 - Construct Binary Tree from Preorder and Inorder Traversal

作者 QIFAN 日期 2017-01-21
LeetCode 105 - Construct Binary Tree from Preorder and Inorder Traversal

原题链接: 105. Construct Binary Tree from Preorder and Inorder Traversal

超级开心从一团乱麻到清晰的分解了问题。


题干

给定一棵树先序遍历与中序遍历,重构树。树中没有重复元素。

思路

树的题目一般会想到用递归做,因为结构相似,任何一个节点都可以看成 父-左-右 的结构。

回忆一下先序遍历:父->左->右。中序遍历:左->右->父

首先简化结构,对于一个节点,根据其子树个数,有下列四种情况:

  • 左右孩子都有

    1
    / \
    2 3
  • 只有左孩子

    1
    /
    2
  • 只有右孩子

    1
    \
    3
  • 没有孩子

    1

第一种情况,先序遍历为 [1,2,3] ,中序遍历为 [2,1,3]
第二种情况,先序遍历为 [1,2] ,中序遍历为 [2,1]
第三种情况,先序遍历为 [1,3] ,中序遍历为 [1,3]
第四种情况,先序遍历为 [1] ,中序遍历为 [1]

先序遍历的第一个一定是根节点。设先序遍历数组为 preorder ,当前位置为 prepos ,中序遍历数组为 inorder ,当前位置为 inpos 。

prepos = 0;
inpos = 0;
Node root = new Node(preorder[prepos]);

然后一直 preorder 依次为一串左子树:

while (curr.val != inorder[inpos]) {
left = new Node(preorder[prepos++]);
curr.left = left;
curr = curr.left;
}

然后抽象一下,假设现在到了某一个节点 curr ,如果这时候:
curr.val == inorder[inpos] ,说明这个节点没有左子树或者左子树已经完了,inorder 的位置应该前进一步。

while (parent.val == inorder[inpos]) {
parent = lastParent;
inpos++;
}

这时候如果没有右子树,先序遍历会跳到 curr 父节点的右子树, 中序遍历则会先输出 curr 的父节点,所以若 parent.val == inorder[inpos] ,那 inorder 的位置再前进一步,parent 也再向上一级,直到没有 parent 为止。

inpos++;

如果有右子树,那 preorder 当前位置就是 curr 右节点的值。

right = new Node(preorder[prepos++]);
curr.right = right;

上述情况中,需要的变量有 curr , preorder , prepos , inorder , inpos ,以及一个储存 parent 的栈。稍微注意一下数组边界,调整结构后代码如下。

时间复杂度为 $O(N)$ ,空间复杂度 worst case (树只有左边一条平的) 为 $O(N)$ 。

代码:

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
int prepos = 0;
int inpos = 0;
// 根节点
TreeNode root = new TreeNode(preorder[prepos++]);
// 用于存储父节点
Stack<TreeNode> stack = new Stack<>();
buildTree(root, stack, preorder, prepos, inorder, inpos);
return root;
}
private void buildTree(TreeNode curr, Stack<TreeNode> stack, int[] preorder, int prepos, int[] inorder, int inpos) {
// base case
if (prepos == preorder.length) {
return;
}
// 直到遍历到最左
while (curr.val != inorder[inpos]) {
// 把父节点们存入栈
stack.push(curr);
curr.left = new TreeNode(preorder[prepos++]);
curr = curr.left;
// 注意数组边界
if (prepos == preorder.length) {
return;
}
}
inpos++;
// 当节点没有右孩子
while (!stack.isEmpty() && stack.peek().val == inorder[inpos]) {
inpos++;
curr = stack.pop();
}
curr.right = new TreeNode(preorder[prepos++]);
curr = curr.right;
buildTree(curr, stack, preorder, prepos, inorder, inpos);
}