本文共 2403 字，大约阅读时间需要 8 分钟。
c/c++ leetcode 1022. 从根到叶的二进制数之和
一:题目描述
难度简单65
给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
以 10^9 + 7 为模，返回这些数字之和。
示例：
输入：[1,0,1,0,1,0,1]输出：22解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
提示：
- 树中的结点数介于
1和1000之间。 - node.val 为
0或1。
解法一: 递归
①如果是，不管是左移还是右移都是“逻辑移位”
例如，分别对无符号数179做左移、右移操作的结果，
图1 逻辑左移
图2 逻辑右移
②如果是，则做左移运算，即做的是“逻辑移位”，同 ①中无符号数的左移。而做右移运算，那么做的是“算术移位”。
图3 带符号位1的算术右移
这里的进位位C，它就是标志寄存器（即状态寄存器，亦称程序状态字寄存器PSW）中的那个进位位，指示是否有进位或者借位，若有则该位为1，否则为0。逻辑左移跟算术左移完全一样。而逻辑右移跟算术右移则不一样，逻辑右移的最高位在移出后补0，而在算术右移中，最高位（这里的最高位指整个编码的最高位，即有符号数的符号位）不变，其他跟逻辑右移一样。
算术左移和算术右移主要用来进行有符号数的倍增、减半； 逻辑左移和逻辑右移主要用来进行无符号数的倍增、减半。
有符号和无符号的算术左移虽然方式是一样的，但他们表示的移位后数的范围是不一样的，有符号数左移（算术左移）位后的范围是-128——127【指8位】。而无符号数（算术左移）左移的范围是0——255【指8位】。
有时间好好研究一下位运算,
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Mdtwj0oZ-1597841241231)(D:\桌面截图\QQ截图20200819184722.png)]
class Solution {public: int sumRootToLeaf(TreeNode* root) { return root ? helper(root,0): NULL; } int helper(TreeNode* root, int num) { if (!root) return 0; //总和 int sum = 0; //num << 1; 左移一位 就这个而言最高位是1 符号位,算术左移;整体进一位,多出来的补零; num = (num << 1) + root -> val; //terminator终止条件 是否是子节点 if (!root -> left && !root -> right) return num; sum += helper(root -> left,num); sum += helper(root -> right,num); return sum; } }; 时空复杂度:
时间复杂度为: 要遍历整个二叉搜索树 为O(N)
空间复杂度为: 最坏复杂度为O(N) 所有的根节点都只有一个左子树或者一个右子树;
解法二: 广度优先搜索
我现在主要练习的是递归的运用 所以就直接看题解了链接:https://leetcode-cn.com/problems/sum-of-root-to-leaf-binary-numbers/solution/mei-kan-dao-ji-ge-bfsde-lai-bu-yi-ge-by-lc080113/
class Solution {public: int sumRootToLeaf(TreeNode* root) { if (!root) return 0; int sum = 0; queue > q; q.push({root,root -> val}); while (!q.empty()) { TreeNode* curr = q.front().first; int currVal = q.front().second; q.pop(); if (!curr -> left && !curr -> right) sum += currVal; if (curr -> left) q.push({curr -> left,(currVal << 1) + curr -> left -> val }); if (curr -> right) q.push({curr -> right,(currVal << 1) + curr -> right -> val }); } return sum; }}; t) q.push({curr -> right,(currVal << 1) + curr -> right -> val });
}return sum;}
};
转载地址：http://vdyki.baihongyu.com/