当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.1028.Recover a Tree From Preorder Traversal 从先序遍历还原二叉树

LeetCode.1028.Recover a Tree From Preorder Traversal 从先序遍历还原二叉树

题目描述

1028 Recover a Tree From Preorder Traversal
https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/

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

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

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

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

示例 1:

      01
  02      05
03  04  06  07

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

示例 2:

              01
      02              05
  03      ##      06      ##
04  ##  ##  ##  07  ##  ##  ##

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

示例 3:

              01
      401              ##
  349      88      ##      ##
90  ##  ##  ##  ##  ##  ##  ##

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

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


解题过程

递归深度优先搜索DFS

利用递归进行先序遍历,遍历的过程中构造二叉树。
定义递归方法 dfs(TreeNode parent, int level),其中 parent 是父节点,level 是父节点的深度,每次读取序列开头的深度 level 和结点值 value,如果 level 是父节点的下一层,就作为父节点的左孩子,继续递归。递归回来后判断如果还有父节点的下一层,就作为右孩子。

先序遍历序列中,相邻的两个节点 a, b 可能的关系有:
1、b 是 a 的左孩子
2、b 是 a 的右孩子(题目中排除了这种情况,当只有一个孩子结点时一定是左孩子)
3、b 是 a 的父节点路径上某个结点的右孩子

时间复杂度 O(n),空间复杂度 O(n)

private static class SolutionV202006 {
    // 解析后的先序遍历结点 list,list 中存放的是二元组 {深度, 结点值}
    LinkedList<int[]> nodeList = new LinkedList<>();
    public TreeNode recoverFromPreorder(String s) {
        // 解析输入的先序序列字符串
        parseInput(s);
        if (nodeList.isEmpty()) {
            return null;
        }
        TreeNode root = new TreeNode(nodeList.peekFirst()[1]);
        nodeList.removeFirst();
        // 深度优先遍历构造二叉树
        dfs(root, 0);
        return root;
    }

    // 深度优先遍历构造二叉树, parent 是父节点, level 是父节点的深度
    public void dfs(TreeNode parent, int level) {
        // 当前先序序列首节点的深度等于 父节点深度+1 时,生成左孩子结点并继续 DFS
        if (!nodeList.isEmpty() && nodeList.peekFirst()[0] == level + 1) {
            TreeNode left = new TreeNode(nodeList.peekFirst()[1]);
            parent.left = left;
            nodeList.removeFirst(); // 删除访问过的序列结点
            dfs(left, level + 1);
        }
        // 当前先序序列首节点的深度等于 父节点深度+1 时,生成右孩子结点并继续 DFS
        if (!nodeList.isEmpty() && nodeList.peekFirst()[0] == level + 1) {
            TreeNode right = new TreeNode(nodeList.peekFirst()[1]);
            parent.right = right;
            nodeList.removeFirst(); // 删除访问过的序列结点
            dfs(right, level + 1);
        }
    }

    // 解析先序遍历字符串,将二元组 {深度, 结点值} 存入 list
    private void parseInput(String s) {
        for (int i = 0; i < s.length();) {
            int level = 0;
            int value = 0;
            while (i < s.length() && s.charAt(i) == '-') {
                level++;
                i++;
            }
            while (i < s.length() && s.charAt(i) != '-') {
                value = value * 10 + s.charAt(i) - '0';
                i++;
            }
            nodeList.add(new int[] {level, value});
        }
    }
}

GitHub代码

algorithms/leetcode/leetcode/_1028_RecoverTreeFromPreorderTraversal.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_1028_RecoverTreeFromPreorderTraversal.java


上一篇 LeetCode.125.Valid Palindrome 验证回文串

下一篇 LeetCode.1014.Best Sightseeing Pair 最佳观光组合

阅读
评论
823
阅读预计4分钟
创建日期 2020-06-18
修改日期 2020-06-18
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论