Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1022.html
1022. Sum of Root To Leaf Binary Numbers (Easy)
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.
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
and1000
. - node.val is
0
or1
. - The answer will not exceed
2^31 - 1
.
Companies:
Amazon
Related Topics:
Tree
Solution 1.
-
/** * 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; Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>(); Queue<Integer> numQueue = new LinkedList<Integer>(); nodeQueue.offer(root); numQueue.offer(root.val); while (!nodeQueue.isEmpty()) { TreeNode node = nodeQueue.poll(); int num = numQueue.poll(); TreeNode left = node.left, right = node.right; if (left == null && right == null) sum += num; else { if (left != null) { nodeQueue.offer(left); numQueue.offer(num * 2 + left.val); } if (right != null) { nodeQueue.offer(right); numQueue.offer(num * 2 + right.val); } } } return sum; } } ############ /** * 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 dfs(root, 0); } private int dfs(TreeNode root, int t) { if (root == null) { return 0; } t = (t << 1) | root.val; if (root.left == null && root.right == null) { return t; } return dfs(root.left, t) + dfs(root.right, t); } }
-
// OJ: https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/ // Time: O(N) // Space: O(H) class Solution { public: int sumRootToLeaf(TreeNode* root, int pre = 0) { if (!root) return 0; int val = (pre << 1) + root->val; if (!root->left && !root->right) return val; return sumRootToLeaf(root->left, val) + sumRootToLeaf(root->right, val); } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sumRootToLeaf(self, root: TreeNode) -> int: def dfs(root, t): if root is None: return 0 t = (t << 1) | root.val if root.left is None and root.right is None: return t return dfs(root.left, t) + dfs(root.right, t) return dfs(root, 0) ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def sumRootToLeaf(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 self.res = 0 self.dfs(root, root.val) return self.res def dfs(self, root, preSum): if not root.left and not root.right: self.res = (self.res + preSum) % (10 ** 9 + 7) return if root.left: self.dfs(root.left, preSum * 2 + root.left.val) if root.right: self.dfs(root.right, preSum * 2 + root.right.val)
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func sumRootToLeaf(root *TreeNode) int { var dfs func(root *TreeNode, t int) int dfs = func(root *TreeNode, t int) int { if root == nil { return 0 } t = (t << 1) | root.Val if root.Left == nil && root.Right == nil { return t } return dfs(root.Left, t) + dfs(root.Right, t) } return dfs(root, 0) }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function sumRootToLeaf(root: TreeNode | null): number { const dfs = (root: TreeNode | null, num: number) => { if (root == null) { return 0; } const { val, left, right } = root; num = (num << 1) | val; if (left == null && right == null) { return num; } return dfs(left, num) + dfs(right, num); }; return dfs(root, 0); }
-
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; impl Solution { fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, mut num: i32) -> i32 { if root.is_none() { return 0; } let root = root.as_ref().unwrap().borrow(); num = (num << 1) | root.val; if root.left.is_none() && root.right.is_none() { return num; } Self::dfs(&root.left, num) + Self::dfs(&root.right, num) } pub fn sum_root_to_leaf(root: Option<Rc<RefCell<TreeNode>>>) -> i32 { Self::dfs(&root, 0) } }