LeetCode-129-求根节点到叶节点数字之和

发表于

「这是我参与11月更文挑战的第26天，活动详情查看：2021最后一次更文挑战」。

求根节点到叶节点数字之和

题目描述：给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

  • 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
    计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/su…

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：递归法

使用递归法解决此问题，递归过程如下：

  • 首先，如果当前节点为null，说明是空树，直接返回；
  • 如果当前节点不是nll，将当前节点的值添加到 path 中；
  • 然后判断当前节点没有左右子节点，说明是叶子节点，将当前的路径值加到result中，然后返回；
  • 如果当前节点的左节点不为空时，递归处理左节点；
  • 如果当前节点的右节点不为空时，递归处理右节点。

最后，返回result即为结果值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
java复制代码import com.kaesar.leetcode.TreeNode;

public class LeetCode_129 {
    // 最终的累加值
    private static int result = 0;

    public static int sumNumbers(TreeNode root) {
        sumNumbers(root, "");
        return result;
    }

    /**
     * 递归法
     *
     * @param root
     * @param path
     */
    private static void sumNumbers(TreeNode root, String path) {
        // 如果当前节点为null，说明是空树，直接返回
        if (root == null) {
            return;
        }
        // 将当前节点的值添加到 path 中
        path += root.val;
        // 如果当前节点没有左右子节点，说明是叶子节点，将当前的路径值加到result中，然后返回
        if (root.left == null && root.right == null) {
            result += Integer.valueOf(path);
            return;
        }
        if (root.left != null) {
            // 当前节点的左节点不为空时，递归处理左节点
            sumNumbers(root.left, path);
        }
        if (root.right != null) {
            // 当前节点的右节点不为空时，递归处理右节点
            sumNumbers(root.right, path);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(9);
        root.right = new TreeNode(0);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(1);

        // 测试用例，期望输出： 1026
        System.out.println(sumNumbers(root));
    }
}

【每日寄语】 人生就像一场赌局，不可能把把都赢，只要筹码在自己手上，就永远都会有希望。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%