LeetCode 106 - Construct Binary Tree from Inorder and Postorder Traversal

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

原题链接: 106. Construct Binary Tree from Inorder and Postorder Traversal


题干

给定一棵树的中序遍历与后序遍历,还原这棵树。

思路

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

乍一看是一道新题,但是如果试着把中序和先序倒过来,便是「右->父->左」和「右->左->父」。这是不是很像用先序和中序重构树?思路讲解看 105. Construct Binary Tree from Preorder and Inorder Traversal ,这里只需把构建左右子树的顺序换一换。

时间复杂度为 $O(N)$ ,空间复杂度最差为 $O(N)$ 。

代码:

public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || inorder.length == 0) {
return null;
}
// 倒序遍历
int inpos = inorder.length - 1;
int postpos = postorder.length - 1;
// 用于存储父节点
Stack<TreeNode> stack = new Stack<>();
TreeNode root = new TreeNode(postorder[postpos--]);
buildTree(root, stack, inorder, postorder, inpos, postpos);
return root;
}
private void buildTree(TreeNode curr, Stack<TreeNode> stack, int[] inorder, int[] postorder, int inpos, int postpos) {
// base case
if (postpos < 0) {
return;
}
// 建立右节点
while (curr.val != inorder[inpos]) {
curr.right = new TreeNode(postorder[postpos--]);
// 把父节点推入栈
stack.push(curr);
curr = curr.right;
if (postpos < 0) {
return;
}
}
inpos--;
while (!stack.isEmpty() && stack.peek().val == inorder[inpos]) {
curr = stack.pop();
inpos--;
}
// 建立左节点
curr.left = new TreeNode(postorder[postpos--]);
curr = curr.left;
buildTree(curr, stack, inorder, postorder, inpos, postpos);
}