589,DFS和BFS解从根到叶的二进制数之和
Confidence grows with success.
越成功越自信。
问题描述
来源:LeetCode第1022题
难度:简单
给出一棵二叉树,其上每个结点的值都是0或1。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如,如果路径为0->1->1->0->1,那么它表示二进制数01101,也就是13。对树上的每一片叶子,我们都要找出从根到该叶子的路径所表示的数字。
返回这些数字之和。题目数据保证答案是一个32位整数。
示例 1:
输入: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
示例 4:
输入:root = [1,1]
输出:3
提示:
树中的结点数介于1和1000之间。
Node.val为0或1。
DFS解决
这里我们先画个图来看一下
我们可以看到从根节点到当前节点这条路径的值就是父节点的值*2加上当前节点的值。我们定义一个全局的变量res,他就是所有从根节点到叶子节点表示数字的和。
我们可以通过前序遍历来解这道题,当遇到叶子节点的时候就把从根节点到当前叶子节点表示的数字加到res中。直接把二叉树的前序遍历方式修改一下即可。
//最终返回的数字
int res = 0;
public int sumRootToLeaf(TreeNode root) {
dfs(root, 0);
return res;
}
//parentPathSum表示从根节点到当前父节点这条路径表示的数字
public void dfs(TreeNode root, int parentPathSum) {
//如果节点为空,直接返回
if (root == null)
return;
//父节点的值*2,在加上当前节点的值就是从根节点到
//当前节点这条路径表示的数字
int sum = parentPathSum * 2 + root.val;
//如果到叶子节点,说明找到了一个从根节点到叶子
//节点的完整路径,把这条路径的值加到res中
if (root.left == null && root.right == null) {
res += sum;
return;
}
//如果没到叶子节点就继续遍历当前节点的左子节点和右子节点
dfs(root.left, sum);
dfs(root.right, sum);
}
时间复杂度:O(N),N是节点的个数,所有节点都要访问一遍
空间复杂度:O(H),H是树的最大高度,也是栈的深度
BFS解决
除了DFS,我们还可以使用BFS来解决,DFS就是深度优先搜索,BFS就是广度优先搜索,具体也可以看下373,数据结构-6,树。BFS就是一层一层的访问。这里需要使用两个队列:
一个存放节点
一个存放从根节点到当前节点这条路径表示的数字
如果访问到叶子节点的时候就把表示的数字加入到res中,最后返回res即可,我们来看下代码。
public int sumRootToLeaf(TreeNode root) {
int res = 0;//结果值
//两个队列,一个存放节点,一个存放从根节点到当前
//节点的父节点这条路径所表示的数字
Queue<TreeNode> queueNode = new LinkedList<>();
Queue<Integer> queueParentSum = new LinkedList<>();
queueNode.add(root);
queueParentSum.add(0);
while (!queueNode.isEmpty()) {
TreeNode cur = queueNode.poll();
int parentSum = queueParentSum.poll();
//计算从根节点到当前节点这条路径表示的数字
int sum = parentSum * 2 + cur.val;
//如果当前节点是叶子节点,就把sum加到res中
if (cur.left == null && cur.right == null) {
res += sum;
continue;
}
//如果左子节点不为空,就把他和他对应的值分别加入
//到对应的队列中
if (cur.left != null) {
queueNode.add(cur.left);
queueParentSum.add(sum);
}
//右子节点同上
if (cur.right != null) {
queueNode.add(cur.right);
queueParentSum.add(sum);
}
}
return res;
}
时间复杂度:O(N),N是节点的个数,所有节点都要访问一遍。
空间复杂度:O(N),这里使用了两个队列,因为队列中元素不停的进和出,最差情况下是满二叉树,到叶子节点的时候每个队列使用的空间是整颗树节点的一半(N/2)
截止到目前我已经写了500多道算法题了,为了方便大家阅读,我把部分算法题整理成了pdf文档,目前有1000多页,大家可以在公众号中回复关键字“pdf”即可获取下载链接。