递归求解
这题让判断从根节点到叶子节点的所有路径中，有没有和等于sum的，如果看过之前讲的《442，剑指 Offer-回溯算法解二叉树中和为某一值的路径》 ，再来看这一题就觉得这题有点简单了。第442题要求的是把所有的和等于sum的路径都打印出来，而这题只要判断有一个路径的和等于sum即可。
我们可以从根节点往下走，走的时候减去当前节点的值，一直到叶子节点，如果减到最后，值等于叶子节点的值，说明存在这样的结果，直接返回true，否则如果把所有节点都遍历完了也不存在这样的结果，就返回false。我们就以示例为例画个图来看一下
再来看下代码
public boolean hasPathSum(TreeNode root, int sum) {
//如果根节点为空，或者叶子节点也遍历完了也没找到这样的结果，就返回false
if (root == null)
return false;
//如果到叶子节点了，并且剩余值等于叶子节点的值，说明找到了这样的结果，直接返回true
if (root.left == null && root.right == null && sum - root.val == 0)
return true;
//分别沿着左右子节点走下去，然后顺便把当前节点的值减掉，左右子节点只要有一个返回true，
//说明存在这样的结果
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
} 时间复杂度：O（N）：N是节点的个数
空间复杂度：O（H）：H是树的高度
非递归解决
上面使用的是递归的方式，我们还可以使用非递归的方式，在遍历的时候有两种方式，一种是从0开始累加，到叶子节点的时候如果累加的值等于sum，说明存在这样的一条路径。还一种是减，从根节点一直减下去，如果到叶子节点的时候，值等于叶子节点的值，说明也存在这样的一条路径。原理都一样，这里就以加的方式来看下代码该怎么写
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);//根节点入栈
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();//出栈
//累加到叶子节点之后，结果等于sum，说明存在这样的一条路径
if (cur.left == null && cur.right == null) {
if (cur.val == sum)
return true;
}
//右子节点累加，然后入栈
if (cur.right != null) {
cur.right.val = cur.val + cur.right.val;
stack.push(cur.right);
}
//左子节点累加，然后入栈
if (cur.left != null) {
cur.left.val = cur.val + cur.left.val;
stack.push(cur.left);
}
}
return false;
} 时间复杂度：O（N）：N是节点的个数
空间复杂度：O（N）：使用一个栈存放树的节点，N是节点的个数
如果大家看过464. BFS和DFS解二叉树的所有路径 ，还可以不直接操作节点的值，可以再使用一个额外的栈，专门存放累加或者往下减的值，这个值是和节点一一对应的，他们会同时出栈，以及同时入栈，实现过程比较简单，这里就不在介绍。
BFS解决
之前在讲373，数据结构-6,树 的时候，讲到树的BFS，就是一层一层的往下打印，像下面这样
他的代码如下
public void levelOrder(TreeNode tree) {
if (tree == null)
return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(tree);//相当于把数据加入到队列尾部
while (!queue.isEmpty()) {
//poll方法相当于移除队列头部的元素
TreeNode node = queue.poll();
System.out.println(node.val);
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
} 在一层一层打印的时候，我们可以把值累加或累减都可以，这里使用累减的方式来看下代码
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
Queue<TreeNode> queue = new LinkedList<>();
root.val = sum - root.val;
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
//累减到根节点之后，结果为0，说明存在这样一条路径，直接返回true
if (node.left == null && node.right == null && node.val == 0)
return true;
//左子节点累减
if (node.left != null) {
node.left.val = node.val - node.left.val;
queue.add(node.left);
}
//右子节点累减
if (node.right != null) {
node.right.val = node.val - node.right.val;
queue.add(node.right);
}
}
return false;
} 时间复杂度：O（N）：N是节点的个数，每个节点都会被访问一遍
空间复杂度：O（N）：使用一个队列，他会记录每一层的节点。
截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
京公网安备 11010502036488号