给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。
叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。
示例 2:
输入:root = [1,2,3], targetSum = 5
输出:false
解释:树中存在两条根节点到叶子节点的路径:
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3:
输入:root = [], targetSum = 0
输出:false
解释:由于树是空的,所以不存在根节点到叶子节点的路径。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
感谢大神windliang的详细解法,传送门详细通俗的思路分析,多解法
- class Solution {
-
- public boolean hasPathSum(TreeNode root, int targetSum) {
- // return hasPathSumI(root, targetSum);
- // return hasPathSumII(root, targetSum);
- // return hasPathSumIII(root, targetSum);
- return hasPathSumIIII(root, targetSum);
- }
-
- //方法四:利用栈后序遍历,进栈时,剩余路径和加;出栈时,剩余路径和减
- //遍历到叶子节点时,计算的路径和是包含整条路径各节点的
- //时间和空间复杂度O(N)
- private boolean hasPathSumIIII(TreeNode root, int targetSum) {
- if (root == null) {
- return false;
- }
- Stack
stack = new Stack<>(); - TreeNode prev = null;
- int curSum = 0;
- while (!stack.isEmpty() || root != null) {
- while (root != null) {
- stack.push(root);
- //入栈时,相加
- curSum += root.val;
- root = root.left;
- }
- TreeNode node = stack.peek();
- if (node.left == null && node.right == null && curSum == targetSum) {
- return true;
- }
- if (node.right != null && node.right != prev) {
- root = node.right;
- } else {
- TreeNode pop = stack.pop();
- //出栈时,减去
- curSum -= pop.val;
- prev = node;
- }
- }
- return false;
- }
-
- //方法三:BFS遍历,定义两个队列,一个进行层序遍历,一个记录根节点到当前节点的累加的和
- //时间和空间复杂度O(N)
- private boolean hasPathSumIII(TreeNode root, int targetSum) {
- if (root == null) {
- return false;
- }
- Queue
queue = new LinkedList<>(); - Queue
queueVal = new LinkedList<>(); - queue.offer(root);
- queueVal.offer(root.val);
- while (!queue.isEmpty()) {
- int size = queue.size();
- while (size-- > 0) {
- TreeNode node = queue.poll();
- Integer curVal = queueVal.poll();
- if (node.left == null && node.right == null && curVal == targetSum) {
- return true;
- }
- if (node.left != null) {
- queue.offer(node.left);
- queueVal.offer(curVal + node.left.val);
- }
- if (node.right != null) {
- queue.offer(node.right);
- queueVal.offer(curVal + node.right.val);
- }
- }
- }
- return false;
- }
-
- //方法二:递归,时间和空间复杂度O(N)
- //根据题意hasPathSum(root, sum)为求解从root到叶子节点的是否存在路径和为sum的路径
- //可以转换成求解从root.left或root.right到叶子节点是否存在路径和为sum-root.val的路径
- private boolean hasPathSumII(TreeNode root, int targetSum) {
- if (root == null) {
- return false;
- }
- //到达叶子节点
- if (root.left == null && root.right == null) {
- return targetSum == root.val;
- }
- return hasPathSumII(root.left, targetSum - root.val)
- || hasPathSumII(root.right, targetSum - root.val);
- }
-
- //方法一:递归,定义全局变量,遍历二叉树
- //时间和空间复杂度O(N)
- boolean hasPathSum = false;
- private boolean hasPathSumI(TreeNode root, int targetSum) {
- if (root == null) {
- return false;
- }
- traverse(root, targetSum, 0);
- return hasPathSum;
- }
-
- private void traverse(TreeNode root, int targetSum, int sum) {
- sum += root.val;
- if (root.left == null && root.right == null && sum == targetSum) {
- hasPathSum = true;
- return;
- }
- if (root.left != null) {
- traverse(root.left, targetSum, sum);
- }
- if (root.right != null) {
- traverse(root.right, targetSum, sum);
- }
- }
- }