Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
You may assume that duplicates do not exist in the tree.
Solution 1: recursive
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n=preorder.length;
return build(preorder,0,n-1,inorder,0,n-1);
}
private TreeNode build(int[] pre, int l1, int h1, int[] in, int l2, int h2) {
if (l1>h1) return null;
TreeNode x=new TreeNode(pre[l1]);
int i=0;
while (in[l2+i]!=pre[l1]) i++;
x.left=build(pre,l1+1,l1+i,in,l2,l2+i-1);
x.right=build(pre,l1+i+1,h1,in,l2+i+1,h2);
return x;
}
}
Solution 2: iterative (use stack)
没有评论:
发表评论