路径总和
树结构如下：
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 | */ |
方法一：递归
1 | class Solution { |
2 | public boolean hasPathSum(TreeNode root, int sum) { |
3 | if(root == null){ |
4 | return false; |
5 | } |
6 | if((sum-root.val != 0) && (root.left==null) && (root.right==null)){ |
7 | return false; |
8 | } |
9 | if((sum-root.val == 0) && (root.left==null) && (root.right==null)){ |
10 | return true; |
11 | } |
12 | return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val); |
13 | } |
14 | |
15 | } |
我们只需要判断当前节点的值是否等于sum - val。
复杂度分析：
- 时间复杂度：$O(N)$，其中$N$是数的节点数，对每个节点访问一次。
- 空间复杂度：$O(H)$，$H$是树的高度，最坏情况是树呈现链状，空间开销为$O(N)$，平均情况下是$O(logN)$。
方法二：广度优先搜索
使用广度优先搜索的方式，记录从根节点到当前节点的路径和，以防止重复计算。
这样我们使用两个队列，分别存储将要遍历的节点，以及根节点到这些节点的路径和即可。
1 | class Solution { |
2 | public boolean hasPathSum(TreeNode root, int sum) { |
3 | if (root == null) { |
4 | return false; |
5 | } |
6 | Queue<TreeNode> queNode = new LinkedList<TreeNode>(); |
7 | Queue<Integer> queVal = new LinkedList<Integer>(); |
8 | queNode.offer(root); |
9 | queVal.offer(root.val); |
10 | while (!queNode.isEmpty()) { |
11 | TreeNode now = queNode.poll(); |
12 | int temp = queVal.poll(); |
13 | if (now.left == null && now.right == null) { |
14 | if (temp == sum) { |
15 | return true; |
16 | } |
17 | continue; |
18 | } |
19 | if (now.left != null) { |
20 | queNode.offer(now.left); |
21 | queVal.offer(now.left.val + temp); |
22 | } |
23 | if (now.right != null) { |
24 | queNode.offer(now.right); |
25 | queVal.offer(now.right.val + temp); |
26 | } |
27 | } |
28 | return false; |
29 | } |
30 | } |
复杂度分析：
- 时间复杂度：$O(N)$。
- 空间复杂度：$O(N)$。