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

---