算法-二叉树DFS-从先序遍历还原二叉树

左手的ㄟ右手 2023-02-19 02:27 26阅读 0赞

# 算法-二叉树DFS-从先序遍历还原二叉树 #

# 1 搜索插入位置 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/

## 1.2 题目描述 ##

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

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

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

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

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]

输入：“1-2–3--4-5–6--7”  
输出：\[1,2,5,3,4,6,7\]

示例 2：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 1]

输入：“1-2–3—4-5–6—7”  
输出：\[1,2,5,3,null,6,null,4,null,7\]

示例 3：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 2]

输入：“1-401–349—90–88”  
输出：\[1,401,null,349,88,90\]

提示：

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

# 2 DFS #

## 2.1 思路 ##

给定字符串是以前序遍历生成，那我们就对应用DFS顺序来遍历字符串来生成树就好了。

每趟DFS结束条件是当前层深度已经不大于下一待处理节点深度，说明需要返回给上一层父节点处理。

## 2.2 代码 ##

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        // 当前遍历的原字符串位置
        private int position = 0;
        // 下一个尚未处理节点的深度
        private int nextD = 0;
        public TreeNode recoverFromPreorder(String S) { 
            return dfs(0, S.toCharArray());
        }
        // 思想：需要获取下一节点的深度，和当前深度对比决定是否能作为子节点
        public TreeNode dfs(int curD, char[] chars){ 
            if(position == chars.length){ 
                return null;
            }
            int curV = 0;
            // 获取当前节点数值
            while(position < chars.length && chars[position] != '-'){ 
                curV = curV * 10 + (chars[position++] - '0');
            }
            // 构建当前节点
            TreeNode curT = new TreeNode(curV);
            // 注意这里要重新计算nextD，因为当前节点就是上一节点的下一处理节点
            nextD = 0;
            // 获取当前下一节点层数
            while(position < chars.length && chars[position] == '-'){ 
                position++;
                nextD++;
            }
            
            if(nextD > curD){ 
                // 仅当下一节点层数大于当前节点，才将下一节点设为当前节点左子树
                curT.left = dfs(nextD, chars);  
            }
            // 这里千万注意，不能放在一个if里面
            // 因为nextD可能在上一个dfs里面已经变化！
            if(nextD > curD){ 
                // 到这里，左子树已经dfs完成，所以当前下一节点自然是本节点右子树
                curT.right = dfs(nextD, chars);     
            }
            return curT;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200618220557549.png]  
O(N)

## 2.4 空间复杂度 ##

O(N)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200618220505389.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020061822051166.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200618220517960.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[20200618220557549.png]: https://img-blog.csdnimg.cn/20200618220557549.png