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.
【分析1-非原创】递归调用。
参考：http://bylijinnan.iteye.com/blog/1355279
public static TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null) {
return null;
}
return build(preorder, 0, preorder.length - 1, inorder, 0,
inorder.length - 1);
}
/*递归建立二叉树，在preorder中获取根节点，在inorder查找根节点，获取一个偏移量offset是左子树的节点个数
* 注意截止条件
* */
public static TreeNode build(int[] preorder, int start1, int end1,
int[] inorder, int start2, int end2) {
if (start1 > end1 || start2 > end2) {
return null;
}
int rootVal = preorder[start1];
TreeNode root = new TreeNode(rootVal);
int divider = getDivider(inorder, start2, end2, rootVal);
int offSet = divider - start2;
TreeNode left = build(preorder, start1 + 1, start1 + offSet, inorder,
start2, start2 + offSet - 1);
TreeNode right = build(preorder, start1 + offSet + 1, end1, inorder,
divider + 1, end2);
root.left = left;
root.right = right;
return root;
}
public static int getDivider(int[] inorder, int start, int end, int arg) {
for (int i = start; i <= end; i++) {
if (inorder[i] == arg) {
return i;
}
}
return -1;
}
【分析1-非原创】辅助Stack。
参考：https://oj.leetcode.com/discuss/2297/the-iterative-solution-is-easier-than-you-think
【LeetCode题目记录-2】从前序遍历和中序遍历构建二叉树
原文：http://blog.csdn.net/brillianteagle/article/details/39294499