LeetCode（Tree)1022. Sum of Root To Leaf Binary Numbers

迷南。 2023-09-26 20:16 96阅读 0赞

# 1.问题 #

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 test cases are generated so that the answer fits in a 32-bits integer.

Example 1:  
![在这里插入图片描述][60abc243c2dfe8865069ee9cb6976c20.png_pic_center]

> 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

Constraints:

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

# 2. 解题思路 #

> 题目要求计算从根节点到叶子节点的所有路径所代表的二进制数之和，可以使用`深度优先搜索来遍历整棵二叉树`，记录下每个节点的二进制值，然后将这些值求和即可。

## 方法1： ##

> 使用递归函数对二叉树进行深度优先搜索  
> 将每个节点的二进制值作为参数传递给递归函数  
> 当递归到叶子节点时，将该节点的二进制值加入到总和中  
> 在递归过程中，可以使用位运算来计算二进制值。

1.先定义一个递归函数 dfs，该函数的参数包括当前节点、当前二进制值和总和。  
2.递归函数中，先将当前节点的二进制值左移一位  
3.然后根据当前节点的值更新二进制值  
4.最后判断当前节点是否为叶子节点，如果是，则将当前二进制值加入到总和中，否则递归遍历当前节点的左右子树。  
5.最后，在主函数中调用递归函数 dfs，并将初始参数设置为根节点、初始二进制值为0和初始总和为0，得到所有路径的二进制值之和

## 方法2： ##

> 1.创建一个 StringBuilder 实例，用于构建二进制字符串。  
> 2.如果输入的二叉树为空，直接返回 0。  
> 3.将当前节点的值添加到 StringBuilder 中。  
> 4.如果当前节点是叶子节点，将 StringBuilder 转换为整数，并删除最后添加的字符。然后返回整数值。  
> 5.如果当前节点不是叶子节点，递归遍历左右子树，将结果累加。然后删除最后添加的字符，并返回累加结果。  
> 需要注意的是，在 StringBuilder 中添加字符时，需要先将其转换为字符串，即使用 String.valueOf(root.val) 方法。在将 StringBuilder 转换为整数时，使用了 Integer.parseInt(strBd.toString(), 2) 方法，将字符串解析为以 2 为基数的整数。此外，在删除最后一个字符时，使用了 strBd.deleteCharAt(strBd.length() - 1) 方法。

## 方法3： ##

> 1.定义一个 ArrayList 用于保存所有从根节点到叶子节点的路径。  
> 2.定义一个递归函数 sumRootToLeafAux，用于遍历二叉树并把从根节点到叶子节点的路径保存到 ArrayList 中。  
> 3.在 sumRootToLeafAux 函数中，首先判断当前节点是否为空，如果为空则返回。  
> 4.如果当前节点不为空，则把当前节点的值添加到临时字符串 temp 中。  
> 5.如果当前节点是叶子节点，则把 temp 添加到 ArrayList 中。  
> 6.如果当前节点不是叶子节点，则递归遍历它的左子树和右子树，并把 temp 传递下去。  
> 7.在主函数 sumRootToLeaf 中，调用 sumRootToLeafAux 函数，并遍历 ArrayList 计算路径所表示的二进制数的和，并返回该和。

# 3. 代码 #

## 代码1： ##

/**
     * 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);
    	}
      public int dfs(TreeNode node, int sum) {
        
    	    if (node == null) {
        
    	        return 0;
    	    }
    	    sum = sum * 2 + node.val; // 当前节点的值加入到路径表示的二进制数中
    	    if (node.left == null && node.right == null) {
         // 当前节点是叶子节点
    	        return sum; // 返回路径表示的二进制数
    	    }
    	    return dfs(node.left, sum) + dfs(node.right, sum); // 递归遍历左右子树
            
        }
    }

> `解释： sum = sum * 2 + node.val; // 当前节点的值加入到路径表示的二进制数中`  
> 这行代码是将当前节点的值 node.val 加入到路径表示的二进制数 sum 中。具体来说，sum 初始值为 0，每当遍历到一个节点时，将其值乘以 2（相当于将其左移一位），然后加上当前节点的值。这样做的目的是将二进制数的每一位对应到二叉树的每一层，而节点的值则对应着二进制数在该层的取值（0 或 1）。例如，对于以下二叉树：  
> ![在这里插入图片描述][11942acd66694f87902d83f40fd288b3.png]  
> 遍历节点 1 时，sum 的值为 1；遍历节点 0 时，sum 的值为 2（1 \* 2 + 0）；遍历节点 0 时，sum 的值为 4（2 \* 2 + 0）；遍历节点 1 时，sum 的值为 5（4 \* 2 + 1）；遍历节点 0 时，sum 的值为 10（5 \* 2 + 0）；遍历节点 1 时，sum 的值为 11（10 \* 2 + 1）。  
> 最终，叶子节点的值代表了一条从根节点到叶子节点的路径所表示的二进制数，而所有叶子节点的路径所表示的二进制数的和即为二叉树所有路径表示的二进制数的和。

> `解释: if (root == null) // 空树的情况 return 0; 为什么返回0`  
> 当输入的二叉树为空时，即 root 为 null，那么此时`没有任何路径可以从根节点到达叶子节点，因此二进制数之和为 0`。因此在这种情况下，函数直接返回 0。  
> 这也是一个常见的做法，在编写递归函数时，通常会先考虑输入为空的情况，也就是递归的终止条件，然后再考虑递归的处理过程。这样可以避免递归过程中出现空指针异常等问题。

class Solution {
        
        public int sumRootToLeaf(TreeNode root) {
        
            if (root == null) // 空树的情况
                return 0;
            
            return sum(root, 0); // 调用 sum 函数计算路径表示的二进制数之和
        }
        
        public int sum(TreeNode root, int sum) {
        
            if (root == null) // 如果遍历到了空节点，返回 0
                return 0;
            
            sum = (sum << 1) + root.val; // 将当前节点的值加入到路径表示的二进制数中
            // 在二进制数中，左移一位相当于乘以 2，右移一位相当于除以 2
            
            if (root.left == null && root.right == null) // 如果遍历到了叶子节点，返回路径表示的二进制数
                return sum;
            
            // 递归遍历左右子树，将其路径表示的二进制数之和返回
            return sum(root.left, sum) + sum(root.right, sum);
        }
    }

> `解释：sum = (sum << 1) + root.val;是什么意思`  
> `sum << 1`表示将 sum 左移一位，相当于将 sum 的二进制表示向左移动一位，然后在右侧填充一个 0。这实际上相当于将 sum 乘以 2。例如，如果 sum 的二进制表示为 101，那么 sum << 1 就是将其左移一位变成 1010，相当于将 101 乘以 2。  
> 接着，将 root.val 加到 sum 上，相当于将 root.val 加到 sum 乘以 2的结果上。这是因为在二进制表示中，左移一位相当于将数值乘以 2，而右移一位相当于将数值除以 2。因此， (sum << 1) + root.val 的结果就是将 root.val 加入到 sum 表示的二进制数中。  
> 例如，如果 sum 的二进制表示为 101，而 root.val 的值为 1，那么 sum = (sum << 1) + root.val 就会将其更新为 1011。

## 代码2： ##

class Solution
    {
        
        private final StringBuilder strBd = new StringBuilder(); // 创建一个 StringBuilder 实例，用于构建二进制字符串
        
        public int sumRootToLeaf(TreeNode root)
        {
        
            if (root == null) // 处理输入为空的情况
            {
        
                return 0;
            }
            strBd.append(String.valueOf(root.val)); // 将当前节点的值添加到 StringBuilder 中
            if (root.left == null && root.right == null) // 如果当前节点是叶子节点，转换为整数并返回
            {
        
                int num = Integer.parseInt(strBd.toString(), 2); // 将 StringBuilder 转换为整数
                strBd.deleteCharAt(strBd.length() - 1); // 删除最后添加的字符
                return num;
            }
            int num = sumRootToLeaf(root.left) + sumRootToLeaf(root.right); // 递归遍历左右子树，并累加结果
            strBd.deleteCharAt(strBd.length() - 1); // 删除最后添加的字符
            return num; // 返回累加结果
        }
    }

> 注释在代码中，主要思路是使用DFS遍历二叉树，遍历的过程中将遍历路径上的节点值拼接起来，形成二进制字符串，最后将这个字符串转化为十进制数并加到结果中。如果当前节点是叶子节点，就将路径转化为十进制数并加到结果中。

class Solution {
        
        int res = 0;
        
        // DFS遍历二叉树的函数
        void traverse(TreeNode node, String sum) {
        
            if (node == null) return;  // 递归终止条件
            
            sum = sum + String.valueOf(node.val);  // 把当前节点的值加入到二进制表示的路径上
            
            if (node.left == null && node.right == null)  // 如果当前节点是叶子节点
                res += Integer.parseInt(sum, 2);  // 将路径转化为十进制数并加到结果中
            
            traverse(node.left, sum);  // 继续遍历左子树
            traverse(node.right, sum); // 继续遍历右子树
        }
        
        public int sumRootToLeaf(TreeNode root) {
        
            traverse(root, "");  // 从根节点开始遍历二叉树
            return res;  // 返回结果
        }
    }

## 代码3： ##

class Solution {
        
        public int sumRootToLeaf(TreeNode root) {
        
            ArrayList<String> arr = new ArrayList<String>(); // 创建一个ArrayList用于存储所有的路径
            sumRootToLeafAux(root, "", arr); // 调用递归函数求解所有的路径
            int ans = 0; // 初始化二进制数之和为0
            for(int i = 0; i<arr.size(); i++){
         // 遍历所有的路径
                ans+=Integer.parseInt(arr.get(i), 2); // 将二进制数转换成十进制数并加到二进制数之和中
            }
            
            return ans; // 返回二进制数之和
        }
        
        public void sumRootToLeafAux(TreeNode node, String temp, List<String> arr) {
         // 递归函数
            if(node!=null){
         // 如果当前节点不为空
                temp += node.val; // 将当前节点的值加到路径中
                if(node.left == null && node.right == null){
         // 如果当前节点是叶子节点
                    arr.add(temp); // 将路径加到ArrayList中
                }
                else{
         // 如果当前节点不是叶子节点
                    sumRootToLeafAux( node.left,  temp,  arr); // 递归遍历左子树
                    sumRootToLeafAux( node.right,  temp,  arr); // 递归遍历右子树
                }
            }
            
        }
    }

[60abc243c2dfe8865069ee9cb6976c20.png_pic_center]: https://img-blog.csdnimg.cn/img_convert/60abc243c2dfe8865069ee9cb6976c20.png#pic_center
[11942acd66694f87902d83f40fd288b3.png]: https://img-blog.csdnimg.cn/11942acd66694f87902d83f40fd288b3.png