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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月17日
下一篇 2020年6月19日

相关推荐

  • leetcode990-等式方程的可满足性

    原题 给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:"a==b" 或 "a!=b"。在这里,a…

    算法 2020年6月8日
    0100
  • leetcode138-复制带随机指针的链表

    这道题和leetcode133-克隆图有异曲同工之妙。 原题 给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。…

    2019年12月17日
    0330
  • leetcode8-字符串转换整数 (atoi)

    原题 请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下: 如果第一个…

    算法 2020年4月3日
    0270
  • leetcode4-寻找两个有序数组的中位数

    这道题我没想出符合条件的思路 原题 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m…

    算法 2020年1月9日
    0620
  • leetcode887-鸡蛋掉落

    原题 你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。 你知道存在楼层 F ,满足 0 &…

    算法 2020年4月11日
    0120
  • leetcode376-摆动序列

    原题 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。 例如, [1,7,4,9,…

    算法 2020年2月18日
    0110
  • 蓝桥杯试题-翻硬币

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 小明正在玩一个“翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写…

    算法 2020年3月1日
    0140
  • leetcode744-寻找比目标字母大的最小字母

    原题 给定一个只包含小写字母的有序数组letters 和一个目标字母 target,寻找有序数组里面比目标字母大的最小字母。 数组里字母的顺序是循环的。举个例子,如果目标字母tar…

    算法 2020年1月5日
    0230
  • leetcode141-环形链表

    原题 给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没…

    2019年12月14日
    0100
  • leetcode409-最长回文串

    原题 给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意:假设字符串的长…

    算法 2020年3月19日
    0570

发表回复

登录后才能评论