[LintCode/LeetCode] Construct Binary Tree from Traversal

2016-8-29 13:24| 发布者: zhangjf| 查看: 651| 评论: 0

摘要: Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder traversal of a tree, construct the binary tree. Notice You may assume that duplicates do not exist in the t ...

Construct Binary Tree from Inorder and Preorder Traversal Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

Notice

You may assume that duplicates do not exist in the tree.

Example

Given in-order [1,2,3] and pre-order [2,1,3], return a tree:

复制代码

Note

许久未更。做了几道二分法的题目练手，发现这道题已经淡忘了，记录一下。

这道题目的要点在于找inorder的区间。preStart每增加一次，就对应一个新的子树。每个子树的根节点都可以在inorder的中间某处找到，以此为界，左边是这个根节点的左子树，右边是右子树。不断递归，得解。

边界条件需要注意：

若preorder或inorder数组为空，返回空；

当preStart前进到超出preorder末位，或inStart超过inEnd，返回空；

每次创建完根节点之后，要将preStart加1，才能进行递归。

Solution

public class Solution {
int preStart = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) return null;
return helper(preorder, inorder, 0, preorder.length-1);
}
public TreeNode helper(int[] preorder, int[] inorder, int inStart, int inEnd) {
if (preStart >= preorder.length || inStart > inEnd) return null;
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == preorder[preStart]) {
index = i;
break;
}
}
TreeNode root = new TreeNode(preorder[preStart++]);
root.left = helper(preorder, inorder, inStart, index-1);
root.right = helper(preorder, inorder, index+1, inEnd);
return root;
}
}

复制代码

Construct Binary Tree from Inorder and Postorder Traversal Problem

Given inorder and postorder traversal of a tree, construct the binary tree.

Notice

You may assume that duplicates do not exist in the tree.

Example

Given inorder [1,2,3] and postorder [1,3,2], return a tree:

复制代码

Note

和先序+中序方法一样，不过这次是逆推，递归的时候先右子树，后左子树即可。

Solution Recursion

public class Solution {
int postEnd;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postEnd = postorder.length - 1;
return helper(postorder, inorder, 0, inorder.length - 1);
}
private TreeNode helper(int[] postorder, int[] inorder, int inStart, int inEnd) {
if (postEnd < 0 || inStart > inEnd) return null;
TreeNode root = new TreeNode(postorder[postEnd--]);
int inMid = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inMid = i;
break;
}
}
root.right = helper(postorder, inorder, inMid +1, inEnd);
root.left = helper(postorder, inorder, inStart, inMid-1);
return root;
}
}

复制代码

Using Stack

public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || inorder.length < 1) return null;
int i = inorder.length - 1;
int p = i;
TreeNode node;
TreeNode root = new TreeNode(postorder[postorder.length - 1]);
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
p--;
while (true) {
if (inorder[i] == stack.peek().val) { // inorder[i] is on top of stack, pop stack to get its parent to get to left side
if (--i < 0) break;
node = stack.pop();
if (!stack.isEmpty() && inorder[i] == stack.peek().val) continue;
node.left = new TreeNode(postorder[p]);
stack.push(node.left);
} else { // inorder[i] is not on top of stack, postorder[p] must be right child
node = new TreeNode(postorder[p]);
stack.peek().right = node;
stack.push(node);
}
p--;
}
return root;
}
}

复制代码

收藏邀请

上一篇：记一次奇怪的debug：Tomcat部署网站每一个页面第一次打开404刷新后才正常显示下一篇：多线程系列之学习多线程下载的基本原理和基本用法（1）

		自动登录	找回密码
密码			立即注册

[LintCode/LeetCode] Construct Binary Tree from Traversal

最新评论

相关分类