Construct Binary Search Tree from Preorder Traversal
Description
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
.)
Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Note:
1 <= preorder.length <= 100
The values of
preorder
are distinct.
Solution
class Solution {
public:
TreeNode *bstFromPreorder(vector<int> &preorder) {
if (preorder.empty())
return nullptr;
TreeNode *node, *curr, *root = new TreeNode(preorder[0]);
stack<TreeNode *> st;
st.push(root);
for (int i = 1; i < preorder.size(); ++i) {
int val = preorder[i];
if (val < st.top()->val) {
node = new TreeNode(val);
st.top()->left = node;
st.push(node);
} else {
do {
curr = st.top();
st.pop();
} while (!st.empty() && st.top()->val < val);
curr->right = new TreeNode(val);
st.push(curr->right);
}
}
return root;
}
};
Last updated