1022. 从根到叶的二进制数之和

不念不忘少年蓝@ 2023-02-18 09:56 14阅读 0赞

# 题目来源 #

[1022. 从根到叶的二进制数之和][1022.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 递归 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
    public static int sumRootToLeaf(TreeNode root) {
        
            if (root == null){
        
                return 0;
            }
    
            int ans = 0;
            List<String> list = new ArrayList<>();
            helper(root, "", list);
            for (String s: list) {
        
                ans += Integer.parseInt(s, 2);
            }
    
            return ans;
        }
    
        private static void helper(TreeNode root, String s, List<String> list){
        
            if (root == null){
        
                return;
            }
    
            s = s + root.val;
    
            if (root.left == null && root.right == null){
        
                list.add(s);
                return;
            }
    
            helper(root.left, s, list);
            helper(root.right, s, list);
        }
    }

![在这里插入图片描述][20200617131552275.png]

class Solution {
        
        public int sumRootToLeaf(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }   
            return dfs(root, 0);
        }
        private int dfs(TreeNode root, int sum){
        
            sum = sum * 2 + root.val;
            if(root.left == null && root.right == null){
        
                return sum;
            }
            if(root.left == null){
        
                return dfs(root.right, sum);
            }
            if(root.right == null){
        
                return dfs(root.left, sum);
            }
            return dfs(root.right, sum) + dfs(root.left, sum);
        }
    }

class Solution {
        
        public int sumRootToLeaf(TreeNode root) {
        
            return helper(root, 0);
        }
    
        private int helper(TreeNode root, int sum){
        
            if(root == null) return 0;
            sum = 2 *sum + root.val;
            if(root.left == null && root.right == null){
        
                return sum;
            }
            return helper(root.left, sum) + helper(root.right, sum);
        }
    }

[1022.]: https://leetcode-cn.com/problems/sum-of-root-to-leaf-binary-numbers/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617132749718.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200617131552275.png]: https://img-blog.csdnimg.cn/20200617131552275.png