每日题解:LeetCode 1028. 从先序遍历还原二叉树

Author Avatar
清水雅然君 06月 18,2020

题目地址

题目描述

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

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

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

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

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

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200618205730271.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWhhbzE5Mg==,size_16,color_FFFFFF,t_70 =300x300)


示例 2:

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

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200618205741637.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWhhbzE5Mg==,size_16,color_FFFFFF,t_70 =300x300)

示例 3:
输入:"1-401--349---90--88"
输出:[1,401,null,349,88,90]

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200618205748895.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWhhbzE5Mg==,size_16,color_FFFFFF,t_70 =300x300)
提示:

原始树中的节点数介于 1 和 1000 之间。
每个节点的值介于 1 和 10 ^ 9 之间。

解法

JAVA 迭代

public class Solution {
    public TreeNode recoverFromPreorder(String S) {
        int len = S.length();
        //"1-2--3--4-5--6--7"
        Stack<TreeNode> stack = new Stack<>();
        int pos = 0;
        while (pos < len) {
            int level = 0;
            while (S.charAt(pos) == '-') {
                pos++;
                level++;
            }
            char value;
            int num = 0;
            while (pos<len && Character.isDigit(value = S.charAt(pos))) {
                num = num * 10 + (value - '0');
                pos++;
            }
            TreeNode node = new TreeNode(num);
                if (level == stack.size()) {
                    if (!stack.isEmpty()) {
                        stack.peek().left = node;
                    }
                }else {
                    while (level != stack.size()){
                        stack.pop();
                    }
                    stack.peek().right= node;
                }
            stack.push(node);
        }
        while (stack.size()>1){
            stack.pop();
        }
        return stack.peek();
    }
   }

CPP 递归


class Solution {
public:
    TreeNode *recoverFromPreorder(string s) {
        return dfs(0, s);
    }
    int pos = 0, level = 0;
    TreeNode *dfs(const int &depth, const string &s) {
        int num = 0;
        for (; pos < s.length() && s[pos]!= '-'; pos++) {
            num = num * 10 + s[pos] - '0';
        }
        level = 0;
        while (pos < s.length() && s[pos] == '-') {
            level++;
            pos++;
        }
        TreeNode *node = new TreeNode(num);
        if (level > depth)
            node->left = dfs(level, s);
        if (level > depth)
            node->right = dfs(level, s);
        return node;

    }

};

解题思路

分析题目可以得到
在这里插入图片描述

  • 字符 - 的个数,表示树的深度:比如-2-5就是深度为1,2是左子树,5是右子树
  • 字符 -的后数字,表示节点的值

迭代

迭代的写法,首先我们先拆分字符得到深度和数字

int pos = 0;
.....
  int level = 0;
  //遍历 -字符
 while (S.charAt(pos) == '-') {
pos++;
level++;
}

由于我们读取的数字字符都是单个的,比如14,我们分别读取到1和4,所以需要*10,进行计算

char value;
int num = 0;
 while (pos<len && Character.isDigit(value = S.charAt(pos))) {
 num = num * 10 + (value - '0');
 pos++;
}

拆完字符 -和数后,我们遇到一个问题,怎么保存我们得到的值,并且可以继续保存往下遍历节点?
我们使用栈,利用栈的后入先出的特点,保存从根节点到当前节点的路径上的所有节点,同时也可以回溯到之前的节点,比如-5就需要回溯到1节点

Stack<TreeNode> stack = new Stack<>();
....遍历代码
stack.push(node);

由于先序遍历的特点,先遍历全部左子树,然后再从最后一个节点开始遍历右节点()
在这里插入图片描述
当我们遍历左子树时,每次遍历一个新节点时,此时的深度level和栈的size()相等,所以我们将节点存入栈,同时将栈顶元素的左子树指向我们当前的节点

 TreeNode node = new TreeNode(num);
if (level == stack.size()) {
if (!stack.isEmpty()) {
stack.peek().left = node;
}

当我们开始遍历右节点的时候,就会出现深度和栈的个数不一致的情况

while (level != stack.size()){
 stack.pop();
}
stack.peek().right= node;

在这里插入图片描述

  • 此时栈的个数为3,深度为2,我们要加入4这个的节点,但是4这个节点和3深度一样的,并且是2的右子树,所以,我们将3节点弹出,同时栈顶节点2的右子树指向当前节点4
  • 同理下一个节点5,深度和栈的个数不一致,我们就继续弹出,直到level和栈的size()相等,然后把栈顶的右子树指向5节点

当我们遍历完字符时.此时栈的情况如下所示,我们需要1这个节点,所以就要把弹出不要的元素,直到栈只有根节点

while (stack.size()>1){
stack.pop();
        }
return stack.peek();

在这里插入图片描述

迭代的最关键思路在这块代码,

  TreeNode node = new TreeNode(num);
                if (level == stack.size()) {
                    if (!stack.isEmpty()) {
                        stack.peek().left = node;
                    }
                }else {
                    while (level != stack.size()){
                        stack.pop();
                    }
                    stack.peek().right= node;
                }
            stack.push(node);

递归

递归的写法,我们先搬出dfs的模板,

public Node dfs(...){

    //...逻辑
    root = ...
    //...逻辑
    root.left = ...
    //...逻辑
    root.right = ...
    //...逻辑
    return root;
}

读取字符的代码和迭代的写法差不多

//全局变量 pos遍历的字符位置
int pos = 0, level = 0;
.....
int num = 0;
//这里可以用whle写,java写法用例while
for (; pos < s.length() && s[pos]!= '-'; pos++) {
            num = num * 10 + s[pos] - '0';
}
level = 0;
 while (pos < s.length() && s[pos] == '-') {
level++;
 pos++;
}

然后套用模板的写法

TreeNode *node = new TreeNode(num);
 //...逻辑
node->left = dfs(level, s);
 //...逻辑
node->right = dfs(level, s);
 //...逻辑
return node;

然后在考虑中止条件,我们使用depth维护当前节点深度,如果level>depth时,表明其存在子节点,则需要继续往前遍历,当level=depth,则返回当前的节点,退回到上一个递归,继续除非其右子树的查找,由于当前的pos已经往后移动了,开始遍历其右节点

  • 比如先遍历1节点,此时我们开始的深度为0,此时level为1,将下一个遍历的值作为其左节点,当遍历完3节点时,此时depth=2,level=2,返回当前节点,退回上一个递归,

在这里插入图片描述

  • 即2节点的右节点查找,
node->right = dfs(level, s);

此时pos指向了4节点,然后depth=1,level=1,返回当前节点,
由于之前2节点之前的depth=1,4读取到字符'-'就一个,,返回当前节点,
在这里插入图片描述

  • 退回上一个递归,依次类推

所以整个递归代码为

static TreeNode *dfs(const int &depth, const string &s) {
        int num = 0;
        for (; pos < s.length() && s[pos]!= '-'; pos++) {
            num = num * 10 + s[pos] - '0';
        }
        level = 0;
        while (pos < s.length() && s[pos] == '-') {
            level++;
            pos++;
        }
        TreeNode *node = new TreeNode(num);
        if (level > depth)
            node->left = dfs(level, s);
        if (level > depth)
            node->right = dfs(level, s);
        return node;

    }