题目描述
返回与给定先序遍历 preorder
相匹配的二叉搜索树(binary search tree)的根结点。
(回想一下,二叉搜索树是二叉树的一种,其每个节点都满足以下规则,对于 node.left
的任何后代,值总 < node.val
,而 node.right
的任何后代,值总 > node.val
。此外,先序遍历首先显示节点的值,然后遍历 node.left
,接着遍历 node.right
。)
样例
输入:[8,5,1,7,10,12]
输出:[8,5,10,1,7,null,12]
提示
1 <= preorder.length <= 100
- 先序
preorder
中的值是不同的。
算法
(栈) $O(n)$
- 我们首先建一个
dummy
结点,值为正无穷。初始时,令当前结点的指针cur
指向它,并将其加入栈中。 - 栈中记录当前还没有右儿子的结点。
- 每次遍历一个新的值,并新建结点。如果当前结点的值小于
cur
指向结点的值,则将它加入到cur
的左儿子。新建结点入栈,cur
更新为当前结点。 - 否则,我们看栈中的结点,如果栈顶结点的值比当前结点的值要小,则栈顶结点出栈,用
cur
来记录出栈的栈顶元素。退出循环后,cur
的右儿子更新为新建的结点。新建结点入栈,cur
更新为当前结点。
时间复杂度
- 每个结点最多进栈一次,出栈一次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要额外的栈空间,故空间复杂度为 $O(n)$。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
int n = preorder.size();
TreeNode *dummy = new TreeNode(INT_MAX);
stack<TreeNode *> st;
st.push(dummy);
TreeNode *cur = dummy;
for (int i = 0; i < n; i++) {
TreeNode *newNode = new TreeNode(preorder[i]);
if (newNode -> val < cur -> val) {
cur -> left = newNode;
} else {
while (st.top() -> val < newNode -> val) {
cur = st.top();
st.pop();
}
cur -> right = newNode;
}
st.push(newNode);
cur = newNode;
}
return dummy -> left;
}
};
妙!