leetcode算法【1028】从先序遍历还原二叉树

我不是女神ヾ 2023-02-18 14:05 2阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：树的前序遍历的模拟
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

我们从二叉树的根节点 root 开始进行深度优先搜索。
    
    在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
    
    如果节点只有一个子节点，那么保证该子节点为左子节点。
    
    给出遍历输出 S，还原树并返回其根节点 root。

示例 1：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70 2]

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

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

#### 方案：树的前序遍历的模拟 ####

*  模拟树的先序遍历即可，代码非最简，仍然可简化，但是效率还是比较高的，用时2ms，超过100%

class Solution { 
            String str;
            int strIndex = 0;
            int depth = 0;
            TreeNode root;
    
            public TreeNode recoverFromPreorder(String S) { 
    
                str = S;
                int val=0;
                while (strIndex<str.length()&&str.charAt(strIndex) != '-') { 
                    val = val*10+str.charAt(strIndex)-'0';
                    strIndex++;
                }
                root = new TreeNode(val);
                root.left = new TreeNode(-1);
                if (!buildTree(1, root.left)) root.left = null;
                root.right = new TreeNode(-1);
                if (!buildTree(1, root.right))root.right=null;
                return root;
            }
    
            public boolean buildTree(int dep, TreeNode node) { 
    
                while (strIndex<str.length()&&str.charAt(strIndex) == '-') { 
                    depth++;
                    strIndex++;
                }
                if (depth == dep) { 
                    int val = 0;
                    while (strIndex<str.length()&&str.charAt(strIndex) != '-') { 
                        val = val*10+str.charAt(strIndex)-'0';
                        strIndex++;
                    }
                    node.val = val;
                    depth = 0;
                    node.left = new TreeNode(-1);
                    if (!buildTree(dep + 1, node.left)) node.left=null;
                    node.right = new TreeNode(-1);
                    if (!buildTree(dep + 1, node.right))node.right=null;
                }else{ return false;}
                return true;
            }
    
        }

##### 复杂度计算 #####

*  时间复杂度：O(n),考虑String的遍历
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200618011020130.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200618011102349.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200618011203695.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh,size_16,color_FFFFFF,t_70