LC1028从先序遍历还原二叉树: DFS+回溯 & 迭代+队列

浏览次数 : 次 2022-01-15

博文字数统计 : 1.9k字 | 阅读所需时长 : 7分

× 文章目录

1. LC1028从先序遍历还原二叉树: DFS+回溯 & 迭代+队列

LeetCode1028：从先序遍历还原二叉树
- 刷题时间：2022-01-15
- 力扣难度：Hard
- 个人难度：Hard-
- 数据结构：字符串、二叉树、双端队列
- 算法：DFS、回溯、迭代
相似题型：LIS问题
- LC105从前序和中序遍历序列构造二叉树：剑指Offer07.重建二叉树
- LC106从中序和后序遍历序列构造二叉树

LC1028从先序遍历还原二叉树: DFS+回溯 & 迭代+队列

1. 题目描述

题目：原题链接
- 我们从二叉树的根节点 root 开始进行深度优先搜索。
- 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。
- 如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0。
- 如果节点只有一个子节点，那么保证该子节点为左子节点。
- 给出遍历输出 S，还原树并返回其根节点 root
输入输出规范
- 输入：根据题意输出的前序序列字符串
- 输出：重建的二叉树根节点
- 数据量
  - 原始树中的节点数介于 1 和 1000 之间。
  - 每个节点的值介于 1 和 10 ^ 9 之间。
输入输出示例
- 输入：”1-2–3—4-5–6—7”
- 输出：root: [1,2,5,3,null,6,null,4,null,7]

2. 方法一：迭代 & 双端队列

思路
- 首先，对于二叉树的题目来说，因为二叉树这种左右节点的结构特点，一般都是通过迭代或者递归的方式求解
- 其中，迭代的具体实现方式一般是通过队列、栈等结构储存每一层的节点，然后进行相应的操作，即BFS的思想，也可以是优先去查找二叉树的一条路径，一直到达其叶子节点，即DFS的思想
- 而递归的思路其实就是把迭代逆向思考，一般也是优先去查找二叉树的一条路径，即DFS
- 对于本题而言，由于题目中明确表示给出的序列是DFS搜索后得到的前序序列，那么自然是运用DFS的思想，既可以使用迭代的方式，也可以使用递归的方式
- 实际上，无论何种方法，本题的核心就是将序列中的短横线与二叉树的深度相关联起来
解题步骤
- 首先，维护一个表示深度的变量depth，对于带有短横线的前序序列的遍历可以通过两种方式进行
  - 遍历字符串，遇到短横线时，深度++，初始值为0，遇到数值时记录数值，注意数值的位数
  - 通过split("-")方法，将字符串拆分为数组并遍历，遇到的元素为空时深度++，此时深度初始值为1，且需要将第一个数值(root元素)先加入队列
- 其次，维护一个队列，队列中用来存放当前遍历的一条二叉树的路径上的所有节点
- 在遍历过程中，对每一个数值元素都判断当前深度与队列中元素个数是否一致
  - 如果一致，表示当前遍历到的元素是下一层的元素(子节点)，根据题意可知将当前元素优先填充到队首元素的左子节点上
  - 如果不一致，实际上一定是队列大小大于当前深度，表示当前元素不是下一层，而是上面某一层的元素，此时不断弹出队列首部的元素，直到队列大小等于深度，此时将当前元素填充到队列首元素的右子节点上
  - 注意，不一致时填充右子节点是因为已经遍历过的层的节点的左子节点一定已经重建过了
  - 同时注意因为弹出的元素应该是后添加的，即后进先出，所以队列添加元素是添加到队首，出队时也从队首出
- 最终遍历结束后的根节点即为重建的二叉树的根节点

题解

public TreeNode recoverFromPreorder(String traversal) {
    TreeNode root = null;
    if (traversal == null || traversal.length() == 0) return root;
    String[] vals = traversal.split("-");
    root = new TreeNode(Integer.parseInt(vals[0]));
    Deque<TreeNode> deque = new LinkedList<>();
    deque.add(root);
    int depth = 1;
    // 构建二叉树的层序遍历输出
    for (int i = 1; i < vals.length; i++) {
        if ("".equals(vals[i])) {
            depth++; // 遇到空串相当于二叉树深度 + 1
        } else { // 数值
            TreeNode cur = new TreeNode(Integer.parseInt(vals[i]));
            // 深度与队列长度一致时，表示队列中放的节点路径到了 depth 深度层，直接连接到左节点
            if (depth == deque.size()) {
                if (!deque.isEmpty()) {
                    deque.peek().left = cur;
                }
            } else {
                // 深度与队列长度不一致时，表示队列中放的节点路径超过了 depth 深度层，取出元素，直到长度相等后在连接到右节点
                while (depth != deque.size()) deque.poll(); // 删除队列中的尾部元素
                deque.peek().right = cur;
            }
            deque.addFirst(cur); // 当前节点加入队列头部
            depth = 1; // 重置深度
        }
    }
    return root;
}

复杂度分析：n 是字符串序列长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$

3. 方法二：递归：DFS & 回溯

解题步骤
- 方法一中已经分析了迭代和递归都可以用来解决本题，这里直接分析下递归的解题步骤
- 首先，递归的DFS方法需要一个深度参数 depth，表示期望添加的元素的深度，其次还需要一个索引参数 index，表示字符串遍历到的位置
- DFS方法中，首先同样是从指定索引开始，在字符串中查找短横线的连续个数，表示当前深度
  - 如果当前深度不等于输入的期望的深度参数 depth，就表示当前元素不是上一轮递归元素的子节点，且上一轮递归元素应该是叶子节点，无子节点(null)，此时根据回溯的思想需要将 index 回退到本次递归前的位置，并返回 null
  - 如果两者相等，那么就查找到字符串的第一个数值元素并创建节点，该节点元素的左右节点分别通过DFS递归去寻找，注意DFS输入的深度+1
- 但是在解题过程中，我们发现在当前深度不等于期望深度时，需要返回 null，而不会再去调用DFS方法递归，即无法将回退的 index 通知到其他地方，所以我们将 index 设为类属性

题解

// 方法二：DFS 递归
int index = 0;
   public TreeNode recoverFromPreorder(String traversal) {
       if (traversal == null || traversal.length() == 0) return null;
       return dfs(traversal, 0);
   }
   
   private TreeNode dfs(String traversal, int depth) {
       int n = traversal.length();
       int curDepth = 0;
       while (index < n && traversal.charAt(index) == '-') {
           curDepth++;
           index++;
       }
       if(curDepth != depth) {
           index -= curDepth; // 如果当前元素所在深度curDepth与目标深度不相等，说明前一个节点没有子节点，当前节点是上一层的子节点
           return null;
       }
       int value = 0;
       while (index < n && Character.isDigit(traversal.charAt(index))) {
           value = value * 10 + (traversal.charAt(index) - '0');
           index++;
       }
       TreeNode cur = new TreeNode(value);
       cur.left = dfs(traversal, depth + 1);
       cur.right = dfs(traversal, depth + 1);
       return cur;
   }

复杂度分析：n 是字符串序列长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$

本文作者： Chthollists
发布时间： 2022-01-15 18:57:24
最后更新： 2022-01-27 20:44:38
本文标题： LC1028从先序遍历还原二叉树: DFS+回溯 & 迭代+队列
本文链接： https://chthollists.github.io/post/93a9edca.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！