题目描述
我们从二叉树的根结点 root
开始进行深度优先搜索。
在遍历中的每个结点处,我们输出 D
条短划线(其中 D
是该结点的深度),然后输出该结点的值。(如果结点的深度为 D
,则其直接子结点的深度为 D + 1
。根结点的深度为 0
)。
如果结点只有一个子结点,那么保证该子节点为左子结点。
给出遍历输出 S
,还原树并返回其根结点 root
。
样例
输入:"1-2--3--4-5--6--7"
输出:[1,2,5,3,4,6,7]
输入:"1-2--3---4-5--6---7"
输出:[1,2,5,3,null,6,null,4,null,7]
输入:"1-401--349---90--88"
输出:[1,401,null,349,88,90]
提示
- 原始树中的节点数介于
1
和1000
之间。 - 每个节点的值介于
1
和10^9
之间。
算法
(栈) $O(n)$
- 我们建立一个栈存储当前路径上的所有结点。初始时建立一个
dummy
结点并放入栈中,然后当前高度depth
设置为-1
。 - 每次读出数字前
-
的个数记为d
(第一个结点个数为0
),然后读出当前数字。 - 如果
depth >= d
,则弹栈直到depth < d
为止。这一步是找到当前结点的父结点的位置。然后新建当前结点。 - 然后如果当前栈顶的父结点左儿子为空,则把新建的结点放到左儿子上,否则放到右儿子上。
- 当前结点进栈,高度
depth
更新为d
。
时间复杂度
- 每个结点最多进栈一次出栈一次,故时间复杂度为 $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* recoverFromPreorder(string S) {
int n = S.length(), cur = 0, depth = -1;
stack<TreeNode*> st;
TreeNode *dummy = new TreeNode(-1);
st.push(dummy);
while (cur < n) {
int d = 0;
while (S[cur] == '-') {
d++;
cur++;
}
int v = 0;
while (cur < n && S[cur] >= '0' && S[cur] <= '9') {
v = v * 10 + S[cur] - '0';
cur++;
}
while (depth >= d) {
st.pop();
depth--;
}
TreeNode *node = new TreeNode(v);
if (st.top() -> left == NULL)
st.top() -> left = node;
else
st.top() -> right = node;
st.push(node);
depth = d;
}
return dummy -> left;
}
};
大佬,这个
cur
表示得是什么?当前字符串遍历到的位置
好滴,AC了,谢谢大佬~