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日

相关推荐

  • leetcode485-最大连续1的个数

    原题 给定一个二进制数组, 计算其中最大连续1的个数。 示例 1: 输入: [1,1,0,1,1,1] 输出: 3 解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是…

    算法 2019年11月20日
    0120
  • 剑指offer44-数字序列中某一位的数字

    原题(来源Leetcode) 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位…

    算法 2020年6月15日
    02870
  • leetcode85-最大矩形

    原题 给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例: 输入: [   ["1","0","1","0","0"…

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

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

    算法 2020年1月20日
    0200
  • leetcode63-不同路径II

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月22日
    0120
  • leetcode47-全排列II

    原题 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 解法 思想 这道题…

    算法 2020年5月10日
    090
  • leetcode77-组合

    原题 给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], […

    算法 2020年5月12日
    0540
  • leetcode138-复制带随机指针的链表

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

    2019年12月17日
    0320
  • leetcode378-有序矩阵中第K小的元素

    原题 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。请注意,它是排序后的第k小元素,而不是第k个元素。 示例: matrix = [ &nbs…

    算法 2020年2月14日
    0420
  • leetcode95-不同的二叉搜索树II

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: [   [1,null,3,2],  &n…

    算法 2020年1月22日
    0700

发表回复

登录后才能评论