来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum/

描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

  1.          5<br />            / \<br />           4   8<br />          /   / \<br />         11  13  4<br />        /  \      \<br />       7    2      1<br />返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

题解

递归

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public boolean hasPathSum(TreeNode root, int sum) {
  12.         if (root == null) return false;
  14.         sum -= root.val;
  15.         if (root.left == null && root.right == null) return 0 == sum;
  17.         return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
  18.     }
  19. }

复杂度分析

  • 时间复杂度：我们访问每个节点一次，时间复杂度为112. 路径总和(Path Sum) - 图1，其中112. 路径总和(Path Sum) - 图2是节点个数。

  • 空间复杂度：最坏情况下，整棵树是非平衡的，例如每个节点都只有一个孩子，递归会调用112. 路径总和(Path Sum) - 图3（树的高度）次，因此栈的空间开销是112. 路径总和(Path Sum) - 图4。但在最好情况下，树是完全平衡的，高度只有112. 路径总和(Path Sum) - 图5，因此在这种情况下空间复杂度只有112. 路径总和(Path Sum) - 图6。

    迭代

    1. /**
    2. * Definition for a binary tree node.
    3. * public class TreeNode {
    4. *     int val;
    5. *     TreeNode left;
    6. *     TreeNode right;
    7. *     TreeNode(int x) { val = x; }
    8. * }
    9. */
    10. class Solution {
    11.   public boolean hasPathSum(TreeNode root, int sum) {
    12.       if (root == null) {
    13.           return false;
    14.       }
    16.       Queue<TreeNode> queueNode = new LinkedList<>();
    17.       Queue<Integer> queueVal = new LinkedList<>();
    18.       queueNode.add(root);
    19.       queueVal.add(root.val);
    20.       while (!queueNode.isEmpty()) {
    21.           TreeNode node = queueNode.poll();
    22.           int temp = queueVal.poll();
    23.           if (node.left == null && node.right == null) {
    24.               if (temp == sum) {
    25.                   return true;
    26.               }
    27.               continue;
    28.           }
    29.           if (node.left != null) {
    30.               queueNode.add(node.left);
    31.               queueVal.add(node.left.val + temp);
    32.           }
    33.           if (node.right != null) {
    34.               queueNode.add(node.right);
    35.               queueVal.add(node.right.val + temp);
    36.           }
    37.       }
    39.       return false;
    40.   }
    41. }

    复杂度分析

  • 时间复杂度：112. 路径总和(Path Sum) - 图7，其中112. 路径总和(Path Sum) - 图8是树的节点数。对每个节点访问一次。

  • 空间复杂度：112. 路径总和(Path Sum) - 图9，其中112. 路径总和(Path Sum) - 图10是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。