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.
可以利用preorder的第一个肯定是root的性质,同时找到此点在inorder中对应的位置,从而把这两个数组对应分割成左子树和右子树。
update: 在搜索Positions时可以用二分法,这样最坏Time: O(nlogn)
update: 在搜索Positions时可以用二分法,这样最坏Time: O(nlogn)
public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null || preorder.length == 0) { return null; } return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); } private TreeNode build(int[] preorder, int prestart, int preend, int[] inorder, int instart, int inend) { if (preend < prestart || inend < instart) { return null; } TreeNode root = new TreeNode(preorder[prestart]); int position = 0; for (int i = instart; i <= inend; i++) { if (inorder[i] == preorder[prestart]) { position = i; } } root.left = build(preorder, prestart + 1, prestart + position - instart, inorder, instart, position - 1); root.right = build(preorder, prestart + position - instart + 1, preend, inorder, position + 1, inend); return root; } }
Given inorder and postorder traversal of a tree, construct the binary tree.
public class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if (inorder == null || inorder.length == 0) { return null; } return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1); } private TreeNode build(int[] inorder, int instart, int inend, int[] postorder, int poststart, int postend) { if (inend < instart || postend < poststart) { return null; } TreeNode root = new TreeNode(postorder[postend]); int position = 0; for (int i = instart; i <= inend; i++) { if (inorder[i] == postorder[postend]) { position = i; } } root.left = build(inorder, instart, position - 1, postorder, poststart, poststart + position - instart - 1); root.right = build(inorder, position + 1, inend, postorder, poststart + position - instart, postend - 1); return root; } }
No comments:
Post a Comment