LeetCode/257. 二叉树的所有路径

257. 二叉树的所有路径

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

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

示例 ：

输入:

   1
 /   \
2     3
 \
  5

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

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题还是基于深度优先搜索遍历的框架，我们需要记录每次遍历的结点，一条路径的终止条件就是当前结点是叶结点，即当前的结点的左右子结点都为空。

具体代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<String> result = new LinkedList<>();

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

    private void dfs(TreeNode root, String temp) {
        if (root == null)
            return;
        StringBuilder sb = new StringBuilder(temp);
        sb.append(root.val);

        if (root.left == null && root.right == null) {
            result.add(sb.toString());
        } else {
            sb.append("->");
            dfs(root.left, sb.toString());
            dfs(root.right, sb.toString());
        }
    }
}