力扣第112题：路径总和

力扣第112题：路径总和

标题形貌

给定一个二叉树和一个目的和，判断该树中是否存在从根节点到叶子节点的路径，使得路径上的节点值之和即是给定的目的和。
叶子节点 是指没有子节点的节点。
解题思绪

要办理这个题目，我们可以利用 深度优先搜索（DFS） 或 广度优先搜索（BFS） 来遍历树。最直观的方法是通过 递归 举行深度优先遍历，查抄是否存在从根节点到叶子节点的路径，使得路径和即是目的值。

• 递归 DFS：从根节点开始遍历，对于每个节点，减去当前节点的值，然后递归地查抄左右子树是否存在目的和。如果某个叶子节点的路径和恰好即是目的值，则返回 true，否则返回 false。
  
• 路径和盘算：每次递归时，我们将当前节点的值从目的和中减去，直到找到一个叶子节点，且此时目的和为0，则阐明找到了满足条件的路径。
  

解法步调

• 从根节点开始递归，判断当前节点是否是叶子节点。
  
• 如果当前节点是叶子节点，查抄路径和是否即是目的值。
  
• 如果当前节点不是叶子节点，递归查抄左右子树。
  
• 若找到符合条件的路径，返回 true，否则返回 false。
  

代码实现（C 语言）

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <stdbool.h>
5. // 二叉树节点结构体
6. struct TreeNode {
7.     int val;
8.     struct TreeNode *left;
9.     struct TreeNode *right;
10. };
12. // 递归判断是否存在路径和
13. bool hasPathSum(struct TreeNode* root, int targetSum) {
14.     if (root == NULL) {
15.         return false;  // 空树没有路径
16.     }
17.    
18.     // 如果当前节点是叶子节点
19.     if (root->left == NULL && root->right == NULL) {
20.         return targetSum == root->val;  // 判断当前路径和是否等于目标值
21.     }
22.    
23.     // 递归检查左右子树
24.     targetSum -= root->val;
25.     return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
26. }
28. // 辅助函数：创建树节点
29. struct TreeNode* createNode(int val) {
30.     struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
31.     node->val = val;
32.     node->left = node->right = NULL;
33.     return node;
34. }
36. // 测试代码
37. int main() {
38.     struct TreeNode* root = createNode(5);
39.     root->left = createNode(4);
40.     root->right = createNode(8);
41.     root->left->left = createNode(11);
42.     root->left->left->left = createNode(7);
43.     root->left->left->right = createNode(2);
44.     root->right->left = createNode(13);
45.     root->right->right = createNode(4);
46.     root->right->right->right = createNode(1);
48.     int targetSum = 22;
49.     if (hasPathSum(root, targetSum)) {
50.         printf("There is a path with sum %d.\n", targetSum);
51.     } else {
52.         printf("There is no path with sum %d.\n", targetSum);
53.     }
55.     return 0;
56. }

复制代码

代码剖析

• 树布局：TreeNode 布局体界说了二叉树节点，包罗节点值 val 和左右子树指针 left 和 right。
  
• 递归判断路径和：
  
  
  
  • 如果当前节点为空，返回 false，表现没有路径。
    
  • 如果当前节点是叶子节点，判断路径和是否即是目的值，如果相称则返回 true，否则返回 false。
    
  • 否则，递归盘算左右子树的路径和。
    
  
  
• 创建节点函数：createNode 用于创创建的节点，在 main 函数中用来构建一个测试用的二叉树。
  
• 测试代码：在 main 函数中，我们构造了一个测试用例，并盘算了树中是否存在符合要求的路径。
  

时间复杂度与空间复杂度

• 时间复杂度：O(n)O(n)O(n)，此中 nnn 是二叉树的节点数。每个节点都会被访问一次，且每次访问时举行常数时间的利用。
  
• 空间复杂度：O(h)O(h)O(h)，此中 hhh 是树的高度。递归调用栈的空间复杂度与树的高度成正比，最坏情况下（树退化为链表时），空间复杂度为 O(n)O(n)O(n)，而在平衡树的情况下，空间复杂度为 O(log⁡n)O(\log n)O(logn)。