leetcode如何解決從根到葉的二進制數之和問題

這篇文章主要介紹了leetcode如何解決從根到葉的二進制數之和問題，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

題目

給出一棵二叉樹，其上每個結點的值都是 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);
    }
}

感謝你能夠認真閱讀完這篇文章，希望小編分享的“leetcode如何解決從根到葉的二進制數之和問題”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!