257. 二叉树的所有路径

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

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

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

思路

递归遍历，带上当前节点的路径即可。遇到叶子节点再保存路径。

解法

class Solution {

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        traversal(root, String.valueOf(root.val), result);
        return result;
    }

    public void traversal(TreeNode root, String path, List<String> result) {
        //遇到叶子节点，保存路径，直接返回
        if (root.left == null && root.right == null) {
            result.add(path);
            return;
        }
        if (root.left != null) {
            //并未修改path值，所以不用对path进行回溯
            traversal(root.left, path + "->" + root.left.val, result);
        }
        if (root.right != null) {
            traversal(root.right, path + "->" + root.right.val, result);
        }
    }
}