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

这是今天的每日一题,怎么说呢,一开始看到标题还以为出错了,因为先序遍历没办法确定一颗二叉树。看了描述之后才明白是怎么回事。感觉这道题虽然是困难,但是思考过程是非常典型的,很多二叉树问题都是这种思考过程。特此记录下来。

题目描述

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

  • 我们从二叉树的根节点 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]

实例 3

1
2
输入:"1-401--349---90--88"
输出:[1,401,null,349,88,90]

提示

  • 原始树中的节点数介于 11000 之间。
  • 每个节点的值介于 110 ^ 9 之间。

思路

不得不说,连续坚持打了一个多月题目后,看见二叉树我就下意识的想到了递归。利用递归来构造子树真的是非常的舒服。

回到这题,首先看到先序遍历,先序遍历是 根节点 -> 左子树 -> 右子树 的遍历过程。所以可以说给你一个字符串,如果这个字符串是可信任的(有按照题目给的要求生成的),第一个数字一定是根节点,然后,后面的两部分中,一部分是左子树,一部分是右子树。

容易发现,字符串右边左右子树字符串开头的 - 数是一样的,因为在同一层,所以我们可以写出初步的思路:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

TreeNode* recoverFromPreorder(string S) {
// 出口条件
if(S.empty()){
return nullptr;
}

int root_value = /*想办法获取 S 第一个数 (除去开头的 - )*/;

auto *root = new TreeNode(root_value);

// 左右子树字符串判定条件为遇到一样多的 -

string left = /*想办法获取左子树的字符串*/
string right = /*想办法获取右子树的字符串*/

// 递归构造子树
root->left = recoverFromPreorder(left);
root->right = recoverFromPreorder(fight);

return root;
}

以上就是初步思路了。但是在获取子树字符串的时候,需要从字符串往后遍历,而递归方法中构造多个 string 会造成效率问题,所以我们可以通过一个 index 指针里指定 子树 字符串开始的位置。并通过引用来移动指针标记子树结束的位置。

同时,我们可以用一个变量来指定当前的层数,并在根节点 - 数量高于 层数-1 的时候结束递归。

递归解法

将思路中最后的优化加上,直接上代码:

  • 语言:C ++
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

class Solution {
public:
TreeNode* recoverFromPreorder(string S) {
if(S.empty()){
return nullptr;
}
int index = 0;
return recover(S ,0 ,index);
}

TreeNode* recover(string &S ,int plies ,int &index){

if(S.empty() || index >= S.size()){
return nullptr;
}

int count = 0;
while(S[index +count] == '-'){
count ++;
}
if(count < plies){
return nullptr;
}
index += count;

int value = 0;
while(index < S.size() && S[index] != '-'){
value *= 10;
value += S[index]-'0';
index ++;

}

auto *t = new TreeNode(value);
t->left = recover(S ,plies +1 ,index);
t->right = recover(S ,plies +1 ,index);
return t;

}
};

重点在于最后面的:

1
2
3
4
auto *t = new TreeNode(value);
t->left = recover(S ,plies +1 ,index);
t->right = recover(S ,plies +1 ,index);
return t;

递归构造子树,同时 层数 +1 ,并且因为 index 是引用变量,所以所有递归方法公用一个指针。

如果是 Java 之类的其他语言可以使用类成员变量来实现,这里就不贴出来了,类似。

结果

迭代解法

说实话我完全没有往迭代的方向去思考,这是力扣官方提供的题解。可以说是手动堆栈来模拟递归了。

其实仔细想想,我的递归解法为尾递归,理论上也是可以转换为迭代的,不过完全没有想到,这里也直接贴官方题解了。

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
class Solution {
public:
TreeNode* recoverFromPreorder(string S) {
stack<TreeNode*> path;
int pos = 0;
while (pos < S.size()) {
int level = 0;
while (S[pos] == '-') {
++level;
++pos;
}
int value = 0;
while (pos < S.size() && isdigit(S[pos])) {
value = value * 10 + (S[pos] - '0');
++pos;
}
TreeNode* node = new TreeNode(value);
if (level == path.size()) {
if (!path.empty()) {
path.top()->left = node;
}
}
else {
while (level != path.size()) {
path.pop();
}
path.top()->right = node;
}
path.push(node);
}
while (path.size() > 1) {
path.pop();
}
return path.top();
}
};
/*
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/solution/cong-xian-xu-bian-li-huan-yuan-er-cha-shu-by-leetc/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
*/

后记

这是一道很典型的二叉树问题,思考的过程主要是思考子树,问题转换为怎么从字符串中找出左子树和右子树的字符串,然后通过递归构造。可以说很多二叉树题目都是类似的思考过程。