专门做游戏的网站,上海建筑设计院,南充房产网,租房网站建设多少钱文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;从根到叶的二进制数之和
出处#xff1a;1022. 从根到叶的二进制数之和
难度
3 级
题目描述
要求
给你二叉树… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题从根到叶的二进制数之和
出处1022. 从根到叶的二进制数之和
难度
3 级
题目描述
要求
给你二叉树的根结点 root \texttt{root} root其中每个结点的值都是 0 \texttt{0} 0 或 1 \texttt{1} 1。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
例如如果路径为 0 → 1 → 1 → 0 → 1 \texttt{0} \rightarrow \texttt{1} \rightarrow \texttt{1} \rightarrow \texttt{0} \rightarrow \texttt{1} 0→1→1→0→1那么它表示二进制数 01101 \texttt{01101} 01101也就是 13 \texttt{13} 13。
对树上的每一个叶结点我们都要找出从根结点到该叶结点的路径所表示的数字。返回这些数字之和。
题目数据保证答案是一个 32 \texttt{32} 32 位整数。
示例
示例 1 输入 root [1,0,1,0,1,0,1] \texttt{root [1,0,1,0,1,0,1]} root [1,0,1,0,1,0,1] 输出 22 \texttt{22} 22 解释 100 (2) 101 (2) 110 (2) 111 (2) 4 5 6 7 22 \texttt{100}_\texttt{(2)} \texttt{101}_\texttt{(2)} \texttt{110}_\texttt{(2)} \texttt{111}_\texttt{(2)} \texttt{4} \texttt{5} \texttt{6} \texttt{7} \texttt{22} 100(2)101(2)110(2)111(2)456722。
示例 2
输入 root [0] \texttt{root [0]} root [0] 输出 0 \texttt{0} 0
数据范围
树中结点数目在范围 [1, 1000] \texttt{[1, 1000]} [1, 1000] 内 Node.val \texttt{Node.val} Node.val 为 0 \texttt{0} 0 或 1 \texttt{1} 1
解法一
思路和算法
为了计算所有的从根到叶的二进制数之和需要对每个叶结点计算从根结点到该叶结点的路径表示的二进制数。可以在遍历路径的过程中计算二进制数。
对于根结点其表示的二进制数即为结点值本身。对于非根结点假设当前结点的值为 val \textit{val} val其父结点对应的二进制数为 prevSum \textit{prevSum} prevSum则当前结点对应的二进制数为 currSum prevSum × 2 val \textit{currSum} \textit{prevSum} \times 2 \textit{val} currSumprevSum×2val。当遇到叶结点时将叶结点对应的二进制数加到二进制数之和即可。
计算每个结点对应的二进制数与计算所有的从根到叶的二进制数之和都可以使用深度优先搜索实现。
计算二叉树的所有从根到叶的二进制数之和时需要分别计算每个非空子树的所有从根到叶的二进制数之和整个过程是一个递归的过程递归的终止条件是当前结点为叶结点。对于其余情况首先计算当前结点对应的二进制数然后对非空子结点调用递归。
代码
class Solution {public int sumRootToLeaf(TreeNode root) {return sumInSubtree(root, 0);}public int sumInSubtree(TreeNode node, int prevSum) {int currSum prevSum * 2 node.val;if (node.left null node.right null) {return currSum;}if (node.left null) {return sumInSubtree(node.right, currSum);}if (node.right null) {return sumInSubtree(node.left, currSum);}return sumInSubtree(node.left, currSum) sumInSubtree(node.right, currSum);}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。每个结点都被访问一次。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间取决于二叉树的高度最坏情况下二叉树的高度是 O ( n ) O(n) O(n)。
解法二
思路和算法
也可以使用广度优先搜索计算所有的从根到叶的二进制数之和。
由于在遍历二叉树的同时需要记录每个结点对应的二进制数因此需要维护两个队列分别存储结点与对应的二进制数。初始时两个队列中分别只有根结点与根结点值。遍历过程中每次从两个队列分别将一个元素出队列这两个出队列的元素是一个结点和该结点对应的二进制数执行如下操作。 如果当前结点是叶结点即左子结点和右子结点都为空则将当前结点对应的二进制数加到二进制数之和。 如果当前结点不是叶结点则每个非空子结点对应的二进制数等于当前结点对应的二进制数乘以 2 2 2 再加上非空子结点值将非空子结点和非空子结点对应的二进制数分别入两个队列。
遍历结束之后即可得到所有的从根到叶的二进制数之和。
代码
class Solution {public int sumRootToLeaf(TreeNode root) {int totalSum 0;QueueTreeNode nodeQueue new ArrayDequeTreeNode();QueueInteger sumQueue new ArrayDequeInteger();nodeQueue.offer(root);sumQueue.offer(root.val);while (!nodeQueue.isEmpty()) {TreeNode node nodeQueue.poll();int sum sumQueue.poll();TreeNode left node.left, right node.right;if (left null right null) {totalSum sum;}if (left ! null) {nodeQueue.offer(left);sumQueue.offer(sum * 2 left.val);}if (right ! null) {nodeQueue.offer(right);sumQueue.offer(sum * 2 right.val);}}return totalSum;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。每个结点都被访问一次。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。空间复杂度主要是队列空间两个队列内元素个数都不超过 n n n。
