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
/ \
2 3
/ / \
4 5 6
前序遍历p0是二叉树的根结点,1是i2,则:
int p = 0;
int[] preorder;
int[] inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
return buildTree(0, preorder.length);
}
TreeNode buildTree(int start, int end) {
if (start >= end) {
return null;
}
TreeNode root = new TreeNode(preorder[p]);
int i;
for (i = start; i < end && preorder[p] != inorder[i]; i++)
;
p++;
root.left = buildTree(start, i);
root.right = buildTree(i + 1, end);
return root;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。