题目描述

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

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

样例

输入:

   1
 /   \
2     3
 \
  5

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

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

算法分析

• 1、从根结点出发，递归走所有的路径，并把路径的值记录下来
• 2、递归过程中
  • 若左子树和右子树都为null，则返回记录的路径s
  • 若左子树不为null，则把左子树的值加入到路径中，递归到左子树
  • 若右子树不为null，则把右子树的值加入到路径中，递归到右子树

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    static List<String> ans = new ArrayList<String>();
    static void dfs(TreeNode root, String s)
    {
        if(root.left == null && root.right == null) 
        {
            ans.add(s);
            return ;
        }
        if(root.left != null) dfs(root.left, s + "->" + root.left.val);
        if(root.right != null) dfs(root.right, s + "->" + root.right.val);
    }
    public List<String> binaryTreePaths(TreeNode root) {
        ans.clear();
        if(root == null) return ans;
        dfs(root, "" + root.val);
        return ans;
    }
}