每日一练：LeeCode-257、二叉树的所有路径【二叉树】

本文是力扣LeeCode-257、二叉树的所有路径学习与理解过程，本文仅做学习之用，对本题感兴趣的小伙伴可以出门左拐LeeCode。

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：[“1->2->5”,“1->3”]

示例 2：

输入：root = [1]
输出：[“1”]

提示：

树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100

思路

1、这道题要求：从根节点到叶⼦的路径，所以一定需要前序遍历，这样容易让⽗节点指向孩⼦节点，找到对应的路径。
2、这道题涉及到了回溯算法，有递归，就会有回溯，我们要把路径记录下来，需要回溯来回退⼀个路径再进⼊另⼀个路径

递归法

1、确定递归函数参数以及返回值

//List<Integer> path : 存放节点值的list，List<String> result ：存放结果路径的list
void getAllPath(TreeNode cur,List<Integer> path,List<String> result)

2、确定递归终⽌条件
本题的终⽌条件是找到叶子结点，当 cur不为空，其左右孩⼦都为空的时候，就找到叶⼦节点。

        if(cur.left==null&&cur.right==null){
            String resPath=""+path.get(0);
            for(int i=1;i<path.size();i++){
                resPath=resPath+"->"+path.get(i);
            }
            result.add(resPath);	//存放结果的list
        }

3、确定单层递归逻辑
1）因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中。

path.add(cur.val);	//void getAllPath(TreeNode cur,List<Integer> path,List<String> result)执行的第一步

2）剩余非叶子节点的递归与回溯过程，代码最好体现出回溯之意，代码不宜过于精简而忽略回溯部分，回溯是因为path 不能⼀直加⼊节点，它还要删节点，然后才能加⼊新的节点

        if(cur.left!=null){
            getAllPath(cur.left,path,result);
            path.remove(path.size()-1);	// 回溯
        }
        if(cur.right!=null){
            getAllPath(cur.right,path,result);
            path.remove(path.size()-1);	// 回溯
        }

整体代码

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if(root==null)return result;
        getAllPath(root,path,result);
        return result;
    }

    void getAllPath(TreeNode cur,List<Integer> path,List<String> result){
        path.add(cur.val);	//中，中为什么写在这⾥，因为最后⼀个节点也要加⼊到path中
        //到了叶⼦节点
        if(cur.left==null&&cur.right==null){
            String resPath=""+path.get(0);
            for(int i=1;i<path.size();i++){
                resPath=resPath+"->"+path.get(i);
            }
            result.add(resPath);
        }
        if(cur.left!=null){		// 左
            getAllPath(cur.left,path,result);
            path.remove(path.size()-1);	// 回溯
        }
        if(cur.right!=null){	// 右
            getAllPath(cur.right,path,result);
            path.remove(path.size()-1);	// 回溯
        }
    }   
}