[leetcode][JAVA]面试题第[1028]题[迭代]

深碍√TFBOYSˉ_ 2023-02-19 02:28 66阅读 0赞

#### 【问题描述】\[困难\] ####

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

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

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

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

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

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

提示：

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

#### 【解答思路】 ####

###### 迭代方法（模拟递归） ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
**时间复杂度：O(N) 空间复杂度：O(N)**

public TreeNode recoverFromPreorder(String S) { 
            Deque<TreeNode> path = new LinkedList<TreeNode>();
            int pos = 0;
            while(pos < S.length()){ 
                int level = 0;
                // 数-
                 while (S.charAt(pos) == '-') { 
                    ++level;
                    ++pos;
                }
            //算数 
            int value =0 ;
            while(pos < S.length() && Character.isDigit(S.charAt(pos)) ){ 
                value = value*10 +(S.charAt(pos)-'0');
                ++pos;
             }
            TreeNode node  =new TreeNode(value);
            //左节点
            if(level == path.size()){ 
                if(!path.isEmpty()){ 
                path.peek().left =node;    
                }
            }
            else{ 
                //找右节点
                while(level!=path.size()){ 
                    path.pop();
                }
            path.peek().right =node; 
            }
            path.push(node);
            }
            while(path.size()>1){ 
                path.pop();
            }
            return path.peek();
        }

#### 【总结】 ####

###### 1.题解里写了「迭代」而不是「递归」的方法。其实可以发现，如果我们用「递归」来实现本题的话，必须也要用到一些全局变量来维护例如「当前遍历到字符串的哪个位置」「下一个节点的深度」这类的信息。这样给我的感觉就像是「在递归的模板上套了一些递归没有办法做的事情」。既然如此的话，我们不如就将递归直接改写成迭代的形式，每次添加一个新节点的时候，就将一些节点从我们自己维护的栈中弹出，将「用栈来遍历树」和「用全局变量实时维护信息」这两者统一起来。 ######

###### 2.以链表组的头一个作为答案的思路有点妙 ######

Deque path = new LinkedList();

###### 3. 栈 ######

pop() 出  
peek() 栈顶  
push() 入

转载链接：https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/solution/cong-xian-xu-bian-li-huan-yuan-er-cha-shu-by-leetc/

参考链接：https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/solution/shou-hui-tu-jie-fei-di-gui-fa-zhong-gou-chu-er-cha/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200618221313386.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200618221323341.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200618221334120.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020061822145644.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200618221741603.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70