Construct Binary Search Tree from Preorder Traversal
从preorder建bst.
这个题要先通过排序找到inorder, 因为inorder中的root在中间, 所以知道左右就是leaf, 通过记录leaf的value, 知道位置, 然后就可以确定bst了.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode bstFromPreorder(int[] preorder) { int[] inorder = new int[preorder.length]; Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < preorder.length; i++) { inorder[i] = preorder[i]; } Arrays.sort(inorder); for(int i = 0; i < inorder.length; i++) { map.put(inorder[i], i); } return toTree(map, preorder, inorder, 0, inorder.length - 1); } int preIndex = 0; private TreeNode toTree(Map<Integer, Integer> map, int[] pre, int[] in, int start, int end) { if(start > end) return null; TreeNode root = new TreeNode(pre[preIndex]); int inIndex = map.get(pre[preIndex]); preIndex++; root.left = toTree(map, pre, in, start, inIndex - 1); root.right = toTree(map, pre, in, inIndex + 1, end); return root; } } |