LeetCode - Easy - 1022. Sum of Root To Leaf Binary Numbers

男娘i 2022-10-17 15:55 42阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/][https_leetcode.com_problems_sum-of-root-to-leaf-binary-numbers]

You are given the `root` of a binary tree where each node has a 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. The answer is **guaranteed** to fit in a **32-bits** integer.

**Example 1:**

![10627780400c7005884f2e09744dc80f.png][]

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

**Example 2:**

Input: root = [0]
    Output: 0

**Example 3:**

Input: root = [1]
    Output: 1

**Example 4:**

Input: root = [1,1]
    Output: 3

**Constraints:**

*  The number of nodes in the tree is in the range `[1, 1000]`.
 *  `Node.val` is `0` or `1`.

## Analysis ##

方法一：递归法。

方法二：迭代法。

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class SumOfRootToLeafBinaryNumbers { 
    
    	//方法一：递归法
        public int sumRootToLeaf(TreeNode root) { 
            int[] sum = { 0};
        	sumRootToLeaf(root, 0, sum);
        	return sum[0];
        }
        
        private void sumRootToLeaf(TreeNode node, int pathSum, int[] sum) { 
        	if(node == null)
        		return;
        	
        	pathSum = (pathSum << 1) | node.val;
        	
        	if(node.left == null && node.right == null)
        		sum[0] += pathSum;
        	
        	sumRootToLeaf(node.left, pathSum, sum);
        	sumRootToLeaf(node.right, pathSum, sum);
        }
        
        //方法二：迭代法
        public int sumRootToLeaf2(TreeNode root) { 
        	int sum = 0;
        	LinkedList<Object[]> stack = new LinkedList<>();
        	stack.push(new Object[] { root, 0});
        	
        	while(!stack.isEmpty()) { 
        		Object[] arr = stack.pop();
        		TreeNode node = (TreeNode)arr[0];
        		int pathSum = (int)arr[1];
        		
        		pathSum = (pathSum << 1) | node.val;
    
        		if(node.left == null && node.right == null)
        			sum += pathSum;
        		
        		if(node.right != null)
        			stack.push(new Object[] { node.right, pathSum});
    
        		if(node.left != null)
        			stack.push(new Object[] { node.left, pathSum});
        	}
        	return sum;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    
    public class SumOfRootToLeafBinaryNumbersTest { 
    
    	@Test
    	public void test() { 
    		SumOfRootToLeafBinaryNumbers obj = new SumOfRootToLeafBinaryNumbers();
    
    		assertEquals(22, obj.sumRootToLeaf(BinaryTree.integers2BinaryTree(1, 0, 1, 0, 1, 0, 1)));
    		assertEquals(0, obj.sumRootToLeaf(BinaryTree.integers2BinaryTree(0)));
    		assertEquals(1, obj.sumRootToLeaf(BinaryTree.integers2BinaryTree(1)));
    		assertEquals(3, obj.sumRootToLeaf(BinaryTree.integers2BinaryTree(1, 1)));
    	}
    	
    	@Test
    	public void test2() { 
    		SumOfRootToLeafBinaryNumbers obj = new SumOfRootToLeafBinaryNumbers();
    		
    		assertEquals(22, obj.sumRootToLeaf2(BinaryTree.integers2BinaryTree(1, 0, 1, 0, 1, 0, 1)));
    		assertEquals(0, obj.sumRootToLeaf2(BinaryTree.integers2BinaryTree(0)));
    		assertEquals(1, obj.sumRootToLeaf2(BinaryTree.integers2BinaryTree(1)));
    		assertEquals(3, obj.sumRootToLeaf2(BinaryTree.integers2BinaryTree(1, 1)));
    	}
    }

[https_leetcode.com_problems_sum-of-root-to-leaf-binary-numbers]: https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/
[10627780400c7005884f2e09744dc80f.png]: /images/20221014/145a8b7c1efd4e4d90f3f34643a5671f.png