257. 二叉树的所有路径

本题来自 LeetCode：257. 二叉树的所有路径^[1]

题目描述

给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明:  叶子节点是指没有子节点的节点。
示例:

输入:

   1
 /   
2     3
 
  5

输出: ["1-2-5", "1-3"]
解释: 所有根节点到叶子节点的路径为: 1-2-5, 1-3

题目分析

本题采用深度优先遍历算法，遍历每条从根节点到叶子节点的路径，并记录路径的内容。

题目解答

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListString binaryTreePaths(TreeNode root) {
        ListString paths = new LinkedList();
        if(root == null) {
            return paths;
        }
        dfs(root, "", paths);
        return paths;
    }
    public void dfs(TreeNode root, String path, ListString paths) {
        // 当前的路径内容
        path = "".equals(path) ? path + root.val : path + "-" + root.val;
        // 表示该节点是根节点
        if(root.left == null && root.right == null) {
            paths.add(path);
            return;
        }
        // 遍历左子节点
        if(root.left != null) {
            dfs(root.left, path, paths);
        }
        // 遍历右子节点
        if(root.right != null) {
            dfs(root.right, path, paths);
        }
    }
}

复杂度分析：
时间复杂度： O(n)，每个节点访问一次
空间复杂度： O(n)，调用栈最大为 n

129. 求根到叶子节点数字之和

本题来自 LeetCode：129. 求根到叶子节点数字之和^[2]

题目描述

给定一个二叉树，它的每个结点都存放一个  0-9  的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1-2-3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明:  叶子节点是指没有子节点的节点。
示例 1:

输入: [1,2,3]
    1
   / 
  2   3
输出: 25
解释:
从根到叶子节点路径 1-2 代表数字 12.
从根到叶子节点路径 1-3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.

示例 2:

输入: [4,9,0,5,1]
    4
   / 
  9   0
 / 
5   1
输出: 1026
解释:
从根到叶子节点路径 4-9-5 代表数字 495.
从根到叶子节点路径 4-9-1 代表数字 491.
从根到叶子节点路径 4-0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

题目分析

本题比较简单，采用深度优先遍历算法，计算出根节点到每个叶子节点路径上的数字之和。

题目解答

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private int sum = 0;

    public int sumNumbers(TreeNode root) {
        if(root == null) {
            return 0;
        }
        dfs(root, 0);
        return sum;
    }

    public void dfs(TreeNode root, int current) {
        // 计算当前的数字
        current = current * 10 + root.val;
        // 叶子节点
        if(root.left == null && root.right == null) {
            sum += current;
            return;
        }
        if(root.left != null) {
            dfs(root.left, current);
        }
        if(root.right != null) {
            dfs(root.right, current);
        }
    }
}

复杂度分析：
时间复杂度： O(n)
空间复杂度： O(n)

参考资料

257. 二叉树的所有路径: https://leetcode-cn.com/problems/binary-tree-paths

258. 求根到叶子节点数字之和: https://leetcode-cn.com/problems/sum-root-to-leaf-numbers

原文始发于微信公众号（xiaogan的技术博客）：