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

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

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) —

推荐阅读：
飞雪迎春作文400字　 我们都在漆黑的“夜”　 勇气真的那么难吗作文900字　 蝴蝶谷作文500字　 聪明的小蚂蚁作文350字　 我本人间柔情客，却把三生尘缘误　 快乐国庆作文150字　 贺进士王参元失火书原文及翻译　 小石城山记原文及翻译　 钴鉧潭西小丘记原文及翻译　
评论列表
添加评论