leetcode1028-从先序遍历还原二叉树

原题

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

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

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

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

示例 1:

leetcode1028-从先序遍历还原二叉树

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

示例 2:

leetcode1028-从先序遍历还原二叉树

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

示例 3:

leetcode1028-从先序遍历还原二叉树

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

提示:

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

解法

思想

好感动。。我也只能写得出这样的困难题了。

用栈来模拟DFS的过程,并记录当前节点的深度和上一个节点的深度,如果当前节点的深度 = 上一个节点的深度+1,那么说明当前节点是上一个节点的子节点,否则需要将栈中的元素弹出。

代码

class Solution {
    public TreeNode recoverFromPreorder(String S) {
        Stack<TreeNode> stack = new Stack<>();
        int num = 0;
        int prevDepth = -1;
        int depth = 0;
        char[] chars = S.toCharArray();
        TreeNode root = null;
        for(int i = 0;i<chars.length;i++){
            // 是数字
            if(Character.isDigit(chars[i])){
                num = num*10+(chars[i]-'0');
                // 若是一个数字的结尾字符
                if(i==chars.length-1 || !Character.isDigit(chars[i+1])){
                    TreeNode node = new TreeNode(num);
                    // 如果depth为0,记录当前节点为根节点
                    if(depth == 0) root = node;
                    // 如果depth不等于prevDepth+1,说明该节点不是上一个节点的子节点,需要从栈中弹出相应的元素个数
                    if(depth != prevDepth + 1){
                        for(int n = 0;n<prevDepth+1-depth;n++)
                            stack.pop();
                    }
                    // 将该节点添加到上一个节点的子节点
                    if(!stack.isEmpty()){
                        TreeNode prev = stack.peek();
                        if(prev.left == null){
                            prev.left = node;
                        }else prev.right = node;
                    }
                    stack.push(node);
                    num = 0;
                    prevDepth = depth;
                    depth = 0;
                }
            }
            // 是中划线,深度+1
            else depth ++;
        }
        return root;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode1028-%e4%bb%8e%e5%85%88%e5%ba%8f%e9%81%8d%e5%8e%86%e8%bf%98%e5%8e%9f%e4%ba%8c%e5%8f%89%e6%a0%91/

发表评论

电子邮件地址不会被公开。