Keshawn_lu's Blog

Leetcode 1028. 从先序遍历还原二叉树

字数统计: 575阅读时长: 2 min
2020/06/18 Share

题目简介:

我们从二叉树的根节点 root 开始进行深度优先搜索。

在遍历中的每个节点处,我们输出 D 条短划线(其中 D 是该节点的深度),然后输出该节点的值。(如果节点的深度为 D,则其直接子节点的深度为 D + 1。根节点的深度为 0)。

如果节点只有一个子节点,那么保证该子节点为左子节点。

给出遍历输出 S,还原树并返回其根节点 root

示例 1:

1
2
输入:"1-2--3--4-5--6--7"
输出:[1,2,5,3,4,6,7]

示例 2:

1
2
输入:"1-2--3---4-5--6---7"
输出:[1,2,5,3,null,6,null,4,null,7]

思路:

利用栈存储节点以及相应的深度。将遍历中遇到的节点及相应的深度依次入栈。

每有一个-,节点的深度就 +1,设当前的节点为node,深度为depth,则node的父节点的深度必为depth - 1。所以每次从栈中弹出数据(即之前所遍历到的节点),直到栈顶元素的深度为depth - 1,此节点便为父节点。

找到父节点后,由于节点只有一个子节点时,那么保证该子节点为左子节点。所以优先设置子节点为父节点的左节点,若已有左节点,则设置为右节点。

tip:

  • 学会make_pair()的使用。

代码如下:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
* 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) {

stack<pair<TreeNode*, int>> stk; //存储结点及相应深度

int root_num = 0;
int i = 0;
while(i < S.length() && S[i] != '-'){

root_num = root_num * 10 + S[i] - '0';
i++;
}
TreeNode* root = new TreeNode(root_num);
stk.push(make_pair(root, 0)); //root深度为0

while(i < S.length()){

int depth = 0;
while(i < S.length() && S[i] == '-'){

depth++;
i++;
}
int num = 0;
while(i < S.length() && S[i] != '-'){

num = num * 10 + S[i] - '0';
i++;
}
TreeNode* node = new TreeNode(num);

while(!stk.empty()){

auto top_node = stk.top();

//不为栈顶结点的子节点
if(depth != top_node.second + 1){

stk.pop();
}
else{
//找到了父节点
if(top_node.first -> left == NULL)
top_node.first -> left = node;
else
top_node.first -> right = node;

stk.push(make_pair(node, depth));
break;
}
}
}

return root;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: