How to Sum the Root To Leaf in Binary Numbers in a Binary Tree u

  • 时间：2020-09-30 16:23:25
  • 分类：网络文摘
  • 阅读：156 次

Given a binary tree, each node has value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 – 1 – 1 – 0 – 1, then this could represent 01101 in binary, which is 13. For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.

binary-tree-binary-numbers How to Sum the Root To Leaf in Binary Numbers in a Binary Tree using Breadth First Search? algorithms BFS c / c++ code coding exercise java

binary-tree-binary-numbers

Example 1:
Input: [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Note:
The number of nodes in the tree is between 1 and 1000.
node.val is 0 or 1.
The answer will not exceed 2^31 – 1.

Breadth First Search Travering the Binary Tree

If we use the BFS (Breadth First Search) algorithm to traverse the binary tree, we get a level-by-level order. At each node, we need to store the current value from the root to the current node. Also, if the current node is a leaf node, we need to add it to the sum.

When we enqueue the child nodes, we can compute the value by multiple the current value and plus the value for the children nodes. The following C++ code implements the BFS algorithm to sum up the values from the root to the leaf nodes.

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        int sum = 0;
        queue<pair<TreeNode*, int>> q;
        if (root == NULL) return 0;
        q.push(make_pair(root, root->val)); // push the root
        while (q.size() > 0) {
            auto p = q.front();
            q.pop();
            TreeNode* node = p.first;
            int cur = p.second;
            if (node->left == NULL && node->right == NULL) { // leaf node
                sum += cur;   
            } else {
               if (node->left != NULL) { // push left children
                   q.push(make_pair(node->left, cur * 2 + node->left->val));
               }
               if (node->right != NULL) { // push right children
                   q.push(make_pair(node->right, cur * 2 + node->right->val));
               }
            }
        }
        return sum;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        int sum = 0;
        queue<pair<TreeNode*, int>> q;
        if (root == NULL) return 0;
        q.push(make_pair(root, root->val)); // push the root
        while (q.size() > 0) {
            auto p = q.front();
            q.pop();
            TreeNode* node = p.first;
            int cur = p.second;
            if (node->left == NULL && node->right == NULL) { // leaf node
                sum += cur;   
            } else {
               if (node->left != NULL) { // push left children
                   q.push(make_pair(node->left, cur * 2 + node->left->val));
               }
               if (node->right != NULL) { // push right children
                   q.push(make_pair(node->right, cur * 2 + node->right->val));
               }
            }
        }
        return sum;
    }
};

When the Binary tree is a singly-directional linked list, the space and time complexity is both O(N). On best cases, the depth of the binary tree is O(logN). The following is a Java equivalent implementation where we use javafx.util.Pair and as you can see, the Java code is quite verbose.

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

import javafx.util.Pair;
 
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        int sum = 0;
        if (root == null) return 0;
        Queue<Pair<TreeNode, Integer>> q = new LinkedList<Pair<TreeNode, Integer>>();
        q.add(new Pair(root, root.val));
        while (!q.isEmpty()) {
            Pair<TreeNode, Integer> p = q.poll(); // pop and return the node from the queue
            TreeNode node = p.getKey();
            int cur = p.getValue();
            if (node.left == null && node.right == null) { // sum up the from root to current leaf node
                sum += cur;
            } else {
                if (node.left != null) { // enqueue the left child
                    q.add(new Pair(node.left, cur * 2 + node.left.val));
                }
                if (node.right != null) { // enqueue the right child
                    q.add(new Pair(node.right, cur * 2 + node.right.val));
                }                
            }            
        }
        return sum;
    }
}
import javafx.util.Pair;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        int sum = 0;
        if (root == null) return 0;
        Queue<Pair<TreeNode, Integer>> q = new LinkedList<Pair<TreeNode, Integer>>();
        q.add(new Pair(root, root.val));
        while (!q.isEmpty()) {
            Pair<TreeNode, Integer> p = q.poll(); // pop and return the node from the queue
            TreeNode node = p.getKey();
            int cur = p.getValue();
            if (node.left == null && node.right == null) { // sum up the from root to current leaf node
                sum += cur;
            } else {
                if (node.left != null) { // enqueue the left child
                    q.add(new Pair(node.left, cur * 2 + node.left.val));
                }
                if (node.right != null) { // enqueue the right child
                    q.add(new Pair(node.right, cur * 2 + node.right.val));
                }                
            }            
        }
        return sum;
    }
}

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
网站结构如何布局，会提高用户体验？　 对于新站来说：如何让网站快速被搜索引擎收录呢？　 网站内部优化细节流程(纯白帽SEO)　 网站安全防止被黑客攻击的办法　 我在落伍的那几年：一个个人站长的回忆录　 给哪些网站暂时赚不到钱的站长鼓鼓劲　 个人站长 建设网站贵在坚持　 网站站长赚钱的6大好用的途径　 整理6款站长赚钱方法 希望对你有所帮助　 个人站长们常见的很多个网站盈利模式总结　
评论列表
添加评论