Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.
Constraints:
1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
The values of preorder are distinct.
-K Himaanshu Shuklaa.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
The values of preorder are distinct.
Algorithm
1). We will write a recursive function constructTree(), which will create a Binary tree from preorder. This function will take preorder, preIndex, min and max.
2). We will first construct the root node of BST which would be the first key in the preorder sequence. But before this we will check if key is greater than min (which is Integer.MIN_VALUE for root node) and less than max(which is Integer.MAX_VALUE for the root node).
3). Call the recursive function for the left sub-tree with keys in the preorder sequence that appears before the i'th index (excluding first index).
4). Call the recursive function for the right sub-tree with keys in the preorder sequence that appears after the i'th index (including i'th index)
1). We will write a recursive function constructTree(), which will create a Binary tree from preorder. This function will take preorder, preIndex, min and max.
2). We will first construct the root node of BST which would be the first key in the preorder sequence. But before this we will check if key is greater than min (which is Integer.MIN_VALUE for root node) and less than max(which is Integer.MAX_VALUE for the root node).
3). Call the recursive function for the left sub-tree with keys in the preorder sequence that appears before the i'th index (excluding first index).
4). Call the recursive function for the right sub-tree with keys in the preorder sequence that appears after the i'th index (including i'th index)
GIT URL: Java Solution of Leet Code's Product of Construct Binary Search Tree From Preorder problem
ALSO CHECK: Other LeetCode Solutions in Java
Java Solution
-K Himaanshu Shuklaa.
No comments:
Post a Comment