题解 | #二叉树中和为某一值的路径(一)#
二叉树中和为某一值的路径(一)
http://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c
第二种思路：
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @param sum int整型
* @return bool布尔型
*/
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;
// }
// }
//第二种方式
// 递归终止条件
if (root == null)
return false;
// 每次递归都减掉经过的结点的值
sum -= root.val;
// 当前结点是叶子结点，并且sum刚好为0，表明该路径和刚好为sum
if (sum == 0 && root.left == null && root.right == null)
return true;
// 保证能递归每个结点，且只需要有一条路径满足即可
// 本质上是DFS深度优先遍历，只是由递归实现
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
}
