Leetcode从根到叶的二进制数之和

叁歲伎倆 2022-10-29 01:59 102阅读 0赞

**[题目描述][Link 1]**

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。返回这些数字之和。题目数据保证答案是一个 32 位 整数。

**示例 1：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70][]

输入：root = \[1,0,1,0,1,0,1\]  
输出：22  
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

**示例 2：**  
输入：root = \[0\]  
输出：0

**示例 3：**  
输入：root = \[1\]  
输出：1

提示：

树中的结点数介于 1 和 1000 之间。  
Node.val 为 0 或 1 。

**解法一：递归**

private static int sumRootToLeaf(TreeNode root) {
            return sumbinary(root, 0);
        }
    
        private static int sumbinary(TreeNode root, int cur) {
            //1、表明刚开始时root就是空的，此时直接返回0
            //2、表明某一颗树的左子树或者右子树为空，不可能同时为空，同时为空不会进入到递归，直接在下面就return了，此种情况为空的那个分支不参与结果的计算，应该直接返回0
            if (root == null) {
                return 0;
            }
            
            //计算结果，等于 2 * cur + root.val
            cur = (cur << 1) + root.val;
    
            //说明已经到叶子接点了
            if (root.left == null && root.right == null) {
                return cur;
            }
            int leftValue = sumbinary(root.left, cur);
            int rightValue = sumbinary(root.right, cur);
    
            return leftValue + rightValue;
        }

**解法二：基于DFS迭代解决**

其实和二叉树的深度优先遍历是类似的，只是此处需要记录遍历之后的值，所以需要两个队列，一个队列用于辅助遍历，一个队列记录迭代到某一个节点时的值，下面以如下二叉树进行说明

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70][]

分析如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1][]

经上面分析，代码如下，代码里面都有注释。

private static int sumRootToLeaf1(TreeNode root) {
            if (root == null) {
                return 0;
            }
    
            //定义一个节点队列(用于辅助进行DFS遍历)
            Queue<TreeNode> nodeQueue = new LinkedList<>();
    
            //定义一个数据队列（用于记录到当前节点时的二进制值，包含当前节点）
            Queue<Integer> dataQueue = new LinkedList<>();
    
            //起始时root 和 root.val 进入队列
            nodeQueue.add(root);
            dataQueue.add(root.val);
    
            //返回值
            int res = 0;
            while (!nodeQueue.isEmpty()) {
                //从两个队列中分别出队一个元素
                TreeNode node = nodeQueue.poll();
                int value = dataQueue.poll();
    
                //如果已经到达叶子节点，则表示找到一个值，直接添加到res中
                if (node.left == null && node.right == null) {
                    res += value;
                } else {
                    //添加左节点
                    // (value << 1) + node.left.val 的解释，比如从跟节点到当前节点node的路劲是1->0，当前节点值是 1 则新值是二进制 101 即 10<<1 + 1
                    if (node.left != null) {
                        nodeQueue.add(node.left);
                        dataQueue.add((value << 1) + node.left.val);
                    }
    
                    //添加右节点
                    if (node.right != null) {
                        nodeQueue.add(node.right);
                        dataQueue.add((value << 1) + node.right.val);
                    }
                }
            }
            return res;
        }

[Link 1]: https://leetcode-cn.com/problems/sum-of-root-to-leaf-binary-numbers
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70]: /images/20221024/6d8cb0b111484db486944dbc4159291a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1]: /images/20221024/9dc7c8d7ee43451d8a7f3d2e62496e59.png