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日

相关推荐

  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升…

    算法 2020年3月21日
    0190
  • leetcode503-下一个更大元素II

    原题 给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,…

    算法 2020年2月1日
    090
  • leetcode430-扁平化多级双向链表

    原题 您将获得一个双向链表,除了下一个和前一个指针之外,它还有一个子指针,可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示…

    2019年12月17日
    090
  • leetcode200-岛屿数量

    原题 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水…

    算法 2019年11月24日
    0150
  • leetcode530-二叉搜索树的最小绝对差

    原题 给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。 示例: 输入:    1    &n…

    算法 2020年2月22日
    01330
  • leetcode173-二叉搜索树迭代器

    原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例: BSTIterator iterator…

    2020年1月16日
    050
  • leetcode24-两两交换链表中的节点

    原题 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例: 给定 1->2->3->…

    算法 2020年1月20日
    0200
  • leetcode11-盛最多水的容器

    原题 给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i,…

    2020年2月27日
    0240
  • leetcode146-LRU缓存机制

    原题 运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。 获取数据 get(key) -…

    算法 2020年5月25日
    0100
  • leetcode9-回文数

    原题 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例1: 输入: 121 输出: true 示例2: 输入: -121 输出: fa…

    算法 2020年2月28日
    0110

发表回复

登录后才能评论