需求：

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

叶子节点 是指没有子节点的节点。
示例 1：

二叉树

输入：root = [1]
输出：["1"]

leetcode题目链接

思路

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

前序遍历以及回溯的过程如图：

回溯

这里我们要优先理解递归遍历的顺序二叉树基础知识。回溯本身就比较抽象，第一次解除很难理解，回溯是递归的反向弹出元素。

递归回溯

/**
 * 257. 二叉树的所有路径
 * 前序遍历
 */
public class BinaryTreePaths {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if(root == null) return result;
        // 单个路径所有元素
        List<Integer> path = new ArrayList<>();
        traversal(result, path, root);
        return result;
    }

    public void traversal(List<String> result, List<Integer> path, TreeNode root) {
        path.add(root.val);// 前序遍历 中
        // 遇到叶子节点，结束本路径遍历
        if (root.left == null && root.right == null) {
            // StringBuilder 运行速度更快
            StringBuilder sb = new StringBuilder();
            // 可以使用size()-1 路径要求是足有节点都为null 视为终点
            for (int i = 0; i < path.size()-1; i++) {
                    sb.append(path.get(i)).append("->");
            }
            sb.append(path.get(path.size()-1));
            result.add(sb.toString());
            return;
        }

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

递归临时变量

//方式二
class Solution {

    List<String> result = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        deal(root, "");
        return result;
    }

    public void deal(TreeNode node, String s) {
        if (node == null)
            return;
        if (node.left == null && node.right == null) {
            // 临时变量拼接字符串
            result.add(new StringBuilder(s).append(node.val).toString());
            return;
        }
        // 临时变量拼接字符串
        String tmp = new StringBuilder(s).append(node.val).append("->").toString();
        deal(node.left, tmp);
        deal(node.right, tmp);
    }
}

层序遍历

// 解法二
class Solution1 {
    /**
     * 迭代法
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) return result;

        Stack<Object> stack = new Stack<>();
        stack.push(root);//节点
        stack.push(root.val + "");// 节点路径
        while (!stack.isEmpty()) {
            // 注意入栈出栈顺序
            String path = (String) stack.pop();
            TreeNode node = (TreeNode) stack.pop();

            //找到叶子节点
            if (node.left == null && node.right == null) {
                result.add(path);
            }
            //左子节点不为null
            if (node.left != null) {
                stack.push(node.left);
                // 重点： 临时变量的使用
                stack.push(path + "->" + node.left.val);
            }
            // 右子节点不为null
            if (node.right != null) {
                stack.push(node.right);
                // 重点： 临时变量的使用
                stack.push(path + "->" + node.right.val);
            }
        }
        return result;
    }
}

后两种方法虽然是递归与层序遍历，但是相似度很高，都是使用临时变量存储，并将临时变量作为参数传到下层递归。

验证结果