257. 二叉树的所有路径

蔚落 2022-11-20 08:21 104阅读 0赞

# 来源 #

[https://leetcode-cn.com/problems/binary-tree-paths/][https_leetcode-cn.com_problems_binary-tree-paths]

# 描述 #

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

# 解析 #

## 深度优先遍历 ##

*  由顶到底遍历二叉树，对于当前节点，只要不是非空节点，就加入路径
 *  判断当前节点是不是叶子节点，如果是说明已经是一条完整路径；如果不是，就继续递归其左右子树构建路径  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]  
    为什么path从3返回2之后，path不是`1->2->3`了，而是又变成了`1->2`呢？
 *  因为`path`不是引用类型，递归`3`执行的是值传递，节点`2`只是把`1->2`这个值传递给了节点`3`，节点`3`对path的修改不会影响节点`2`的`path`

为什么lists从3返回2之后，lists不是`1->2->3`了，而是变成了空？

*  因为`lists`是引用类型，递归`3`执行的是地址传递，节点`3`把`lists`的地址传递给了节点`3`，节点`3`对`lists`的修改会影响节点`2`的`lists`

public  List<String> binaryTreePaths(TreeNode root) {
        
            List<String> list = new LinkedList<>();
            helper(root, "", list);
            return list;
        }
        private  void helper(TreeNode root, String path, List<String> lists){
        
            if(root == null) return ;  // 为空
            path = path + root.val;
            if(root.left == null && root.right == null){
          // 到达叶子节点
                lists.add(str);
            }else{
          // 不是叶子节点, 需要加上"->"，继续递归其左右子树构建路径
                helper(root.left, path + "->", lists);
                helper(root.right, path + "->", lists);
            }
        }

*  遍历所有节点一次且仅访问一次，时间复杂度为O(n)O(n).
 *  递归使用栈辅助空间，空间复杂度为O(n)O(n).

[https_leetcode-cn.com_problems_binary-tree-paths]: https://leetcode-cn.com/problems/binary-tree-paths/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/88eb5854a3f14516919488228c92bb04.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201027193543514.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70#pic_center