【2024考研】题解18 | #二叉树中和为某值的路径I#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        //特例
       if(root == NULL) return false;
        //叶子结点 且 每次递归后目标值减去节点值 差值为0就代表找着了（sum-root->val == 0）
       if(root->left == NULL && root->right == NULL && sum == root->val) return true;
        //左右找吧
       return hasPathSum(root->left,sum - root->val) || hasPathSum(root->right,sum - root->val);

    }
};

基本算法思想：

1. 首先判断特例，如果根节点为空，则返回false。

2. 如果当前节点是叶子节点，并且路径上所有节点的值之和等于目标值，则返回true。

3. 否则，递归地判断左子树和右子树中是否存在满足条件的路径。具体做法是，分别计算当前节点到左子树和右子树的路径上节点值之和与目标值之差，然后递归调用`hasPathSum`函数。

4. 如果左子树或右子树中存在满足条件的路径，则返回true；否则返回false。

时间复杂度：

假设二叉树中有n个节点，每个节点都需要遍历一次，因此时间复杂度为O(n)。

空间复杂度：

递归调用`hasPathSum`函数时，会使用系统栈空间来保存函数调用的上下文信息，递归的深度最多为二叉树的高度，因此空间复杂度为O(h)，其中h是二叉树的高度。在最坏情况下，二叉树是一条链，高度为n，此时空间复杂度为O(n)。