代码随想录刷题学习日记

仅为个人记录复盘学习历程，解题思路来自代码随想录

代码随想录刷题笔记总结网址:
代码随想录

257. 二叉树的所有路径

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

提供参数：根结点root

关键思路：由于需要返回从根节点到叶子节点的路径，故采用前序遍历，每次遍历时将当前节点加入到路径上，在遍历到叶子节点（左右子结点皆为null）的时候将路径加入到结果集中。

主要操作：

递归三要素：

1.返回值类型和传入参数：

传入结果集res，路径path，根结点root，返回值类型为void

2.终止条件：

如果左右子结点皆为空，说明到达叶子节点，执行操作：将路径加入到结果集中。

3.单层递归逻辑：

如果左子节点不为空，在路径上加入"->"，继续遍历左子节点，遍历结束后，将"->"弹出。

如果右子节点不为空，在路径上加入"->"，继续遍历右子节点，遍历结束后，将"->"弹出。

这里由于终止条件判断为左右子节点是否为null，所以将对节点的操作提前到对终止条件的判断前，这样可以将路径的最后一个节点加入到路径中。

代码大致如下：

    public List<String> binaryTreePaths(TreeNode root) {
        List<String>res=new ArrayList<>();
        String path="";
        if(root==null)return res;
        travel(root,path,res);
        return res;
    }

    public void travel(TreeNode root, String path,List<String> res){
        path+=root.val;
        //终止条件
        if(root.left==null&&root.right==null){
            res.add(path);
            return;
        }
        //单层递归操作
        if(root.left!=null){
            path+="->";
            travel(root.left,path,res);
            path=path.substring(0,path.length()-2);
        }
        if(root.right!=null){
            path+="->";
            travel(root.right,path,res);
            path=path.substring(0,path.length()-2);
        }
    }