Return the root node of a binary search tree that matches the given
(Recall that a binary search tree is a binary tree where for every node, any descendant of
It’s guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.
Example 1:
Constraints:
1 <= preorder.length <= 100 1 <= preorder[i] <= 10^8 - The values of
preorder are distinct.
Code
0 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 |
/** * 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 { int i = 0; public TreeNode bstFromPreorder(int[] A) { return bstFromPreorder(A, Integer.MAX_VALUE); } public TreeNode bstFromPreorder(int[] A, int bound) { if (i == A.length || A[i] > bound) return null; TreeNode root = new TreeNode(A[i++]); root.left = bstFromPreorder(A, root.val); root.right = bstFromPreorder(A, bound); return root; } } |
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.