leetcode257-二叉树的所有路径

小灰灰 2023-06-14 13:56 9阅读 0赞

### 文章目录 ###

*  二叉树的所有路径
 *   *  题目描述
     *  code
     *   *  方式一

# 二叉树的所有路径 #

## 题目描述 ##

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:
    
       1
     /   \
    2     3
     \
      5
    
    输出: ["1->2->5", "1->3"]
    
    解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

## code ##

### 方式一 ###

> 使用深度优先遍历，dfs方式非常合适

class Solution {
            //
            private List<String> res = new ArrayList<>();
            private List<Integer> path = new ArrayList<>();
            //进行遍历  dfs
            public List<String> binaryTreePaths(TreeNode root) {
                dfs(root); //新建一个函数，使用dfs方式进行遍历
                return res;
            }
    
            private void dfs(TreeNode root) {
                if(root== null){
                    return ;
                }
                path.add(root.val); //将当前节点，添加到path中,用于后序的操作
                //如果深度遍历到达根节点
                if (root.left == null && root.right == null) {
                    StringBuilder sb = new StringBuilder();
                    //此时path中已经记录了一条记录
                    for (int i = 0; i < path.size(); i++) {
                        sb.append(path.get(i));
                        //添加箭头-> 表示连接
                        if (i != path.size() - 1) {
                            sb.append("->");
                        }
                    }
                    //添加到结果集中
                    res.add(sb.toString());
                }
                //递归进行遍历
                dfs(root.left);
                dfs(root.right);
                //删除最后一个节点的值
                path.remove(path.size() - 1);//最后一个，删除
            }
    
        }