leetcode樹之從根到葉的二進制數之和

序

本文主要記錄一下leetcode樹之從根到葉的二進制數之和node

題目

給出一棵二叉樹，其上每一個結點的值都是 0 或 1 。每一條從根到葉的路徑都表明一個從最高有效位開始的二進制數。例如，若是路徑爲 0 -> 1 -> 1 -> 0 -> 1，那麼它表示二進制數 01101，也就是 13 。

對樹上的每一片葉子，咱們都要找出從根到該葉子的路徑所表示的數字。

以 10^9 + 7 爲模，返回這些數字之和。

 

示例：

![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/04/05/sum-of-root-to-leaf-binary-numbers.png)

輸入：[1,0,1,0,1,0,1]
輸出：22
解釋：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

 

提示：

    樹中的結點數介於 1 和 1000 之間。
    node.val 爲 0 或 1 。

來源：力扣（LeetCode）
連接：https://leetcode-cn.com/problems/sum-of-root-to-leaf-binary-numbers
著做權歸領釦網絡全部。商業轉載請聯繫官方受權，非商業轉載請註明出處。

題解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return sumNode(root, 0);
    }

    public int sumNode(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }

        sum = 2 * sum + node.val;

        if (node.left == null && node.right == null) {
            return sum;
        }

        return sumNode(node.left, sum) + sumNode(node.right, sum);
    }
}

小結

這裏採用遞歸的方法，當node爲null時返回0；以後對sum累加當前node.val；若node.left及node.right爲null則返回sum，不然遞歸計算sumNode(node.left, sum)再累加上sumNode(node.right, sum)。網絡

doc

• 從根到葉的二進制數之和