257. 二叉树的所有路径(Binary Tree Paths)

来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-paths/

描述

给定一个二叉树，返回所有从根节点到叶子节点的路径。
示例:
输入:
1
/ \
2 3
\
5
输出: [“1->2->5”, “1->3”]

题解

递归版

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new LinkedList<>();
        construct_paths(root, "", paths);
        return paths;
    }
    public void construct_paths(TreeNode root, String path, List<String> paths) {
        if (null != root) {
            path += Integer.toString(root.val);
            if (root.left == null && root.right == null) {
                paths.add(path);
            } else {
                path += "->";
                construct_paths(root.left, path, paths);
                construct_paths(root.right, path, paths);
            }
        }
    }
}

复杂度分析

• 时间复杂度：每个节点只会被访问一次，因此时间复杂度为，其中表示节点数目；
• 空间复杂度：。在最坏情况下，当二叉树中每个节点只有一个孩子节点时，递归的层数为，此时空间复杂度为。在最好情况下，当二叉树为平衡二叉树时，它的高度为，此时空间复杂度为 ；