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

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

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

推荐阅读：
老虎请客——小花猪6　 揭穿阴谋——小花猪7　 虎狈为奸——小花猪8　 老虎认亲——小花猪9　 跳远比赛——小花猪10　 虎逃狈亡——小花猪11　 真实的虚数　 能被2、5、3、9、4、25、8、125、7、11、13等数整除的数的特征　 哥德巴赫猜想的简介　 我好困好困|小学作文　
评论列表
添加评论