257. 二叉树的所有路径

1、概要

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

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

要求从根节点到叶子的路径，需要前序遍历
涉及到回溯，要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

2、思路

递归法

递归函数参数及返回值

传入根节点，记录路径paths，存放结果集res

private void traversal(TreeNode root,List<Integer> paths,List<String> res)

终止条件

本题要找叶子结点，当cur不为空，其左右孩子都为空的时候

为什么没有判断cur是否为空呢，因为下面的逻辑可以控制空节点不入循环。

if(root.left==null && root.right==null){//遇到叶子节点
    
            StringBuilder sb = new StringBuilder();
            //做路径
            for(int i=0;i<paths.size()-1;i++){
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size()-1));//※
            res.add(sb.toString());
            return;
        }

单层逻辑

回溯和递归是一一对应的，有一个递归，就要有一个回溯，所以回溯要和递归永远在一起。

		if(root.left!=null){//左
            traversal(root.left,paths,res);
            paths.remove(paths.size()-1);
        }
        if(root.right!=null){//右
            traversal(root.right,paths,res);
            paths.remove(paths.size()-1);
        }

迭代法

非递归的方式，我们可以依然可以使用前序遍历的迭代方式来模拟遍历路径的过程可以直接定义一个成员变量为object的栈

3、代码

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if(root == null){return res;}
        List<Integer> paths = new ArrayList<>();
        Stack<Object> stack = new Stack<>();
        traversalIteration(root,stack,res);
        //traversal(root,paths,res);
        return res;
    }
    private void traversalIteration(TreeNode root,Stack<Object> stack,List<String> res){
        stack.push(root);
        stack.push(root.val+"");//Integer转成String
        while(!stack.isEmpty()){
            //出栈，中
            String path = (String)stack.pop();
            TreeNode cur = (TreeNode)stack.pop();

            //左
            if(cur.left!=null){
                stack.push(cur.left);
                stack.push(path + "->" + cur.left.val);//加path和路径
            }
            //右
            if(cur.right!=null){
                stack.push(cur.right);
                stack.push(path + "->" + cur.right.val);
            }
            //叶子结点 
            if(cur.left == null && cur.right==null){
                res.add(path);
            }
        }
    }

    private void traversal(TreeNode root,List<Integer> paths,List<String> res){
        paths.add(root.val);//中
        if(root.left!=null){//左
            traversal(root.left,paths,res);
            paths.remove(paths.size()-1);
        }
        if(root.right!=null){//右
            traversal(root.right,paths,res);
            paths.remove(paths.size()-1);
        }
        if(root.left==null && root.right==null){//遇到叶子节点
            StringBuilder sb = new StringBuilder();
            // StringBuilder用来拼接字符串，速度更快
            //做路径
            for(int i=0;i<paths.size()-1;i++){
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size()-1));//※
            // 记录最后一个节点，因为前面的节点后面要加箭头啊
            res.add(sb.toString());
            // 收集一个路径
            return;
        }
    }
}