乐趣区

关于java:LeetCode129求根节点到叶节点数字之和

jiezi

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

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

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

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

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：递归法

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

  • 首先，如果以后节点为 null，阐明是空树，间接返回；
  • 如果以后节点不是 nll，将以后节点的值增加到 path 中；
  • 而后判断以后节点没有左右子节点，阐明是叶子节点，将以后的门路值加到 result 中，而后返回；
  • 如果以后节点的左节点不为空时，递归解决左节点；
  • 如果以后节点的右节点不为空时，递归解决右节点。

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

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));
    }
}

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

退出移动版