欢迎访问LeetCode题解合集

题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。

叶子节点 是指没有子节点的节点。

示例 1：

[HTML_REMOVED]

[HTML_REMOVED]

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

示例2：

[HTML_REMOVED]

[HTML_REMOVED]

输入：root = [1,2,3], targetSum = 5
输出：false

示例 3：

输入：root = [1,2], targetSum = 0
输出：false

提示：

• 树中节点的数目在范围 [0, 5000] 内
• $-1000 \le Node.val \le 1000$
• $-1000 \le targetSum \le 1000$

题解：

法一：

递归。

自顶向下，每走到一个节点让 targetSum 减去该节点的值，当走到叶节点时，若 targetSum 整好等于 0 ，说明找到一条路径，直接返回即可。

时间复杂度：$O(n)$

额外空间复杂度：平均$O(logn)$，最坏 $O(n)$

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if ( !root ) return false;

        if ( !root->left && !root->right )
            return targetSum == root->val;

        if ( hasPathSum( root->left, targetSum - root->val ) )
            return true;

        return hasPathSum( root->right, targetSum - root->val );
    }
};
/*
时间：12ms，击败：72.72%
内存：20.7MB，击败：20.81%
*/

也可以用非递归来完成：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if ( !root ) return false;
        vector< pair<TreeNode*, int> > stk;
        stk.push_back( {root, targetSum} );
        while ( stk.size() ) {
            auto [root, rest] = stk.back();
            stk.pop_back();
            rest -= root->val;
            if ( !root->left && !root->right && !rest )
                return true;
            if ( root->right ) stk.push_back( {root->right, rest} );
            if ( root->left ) stk.push_back( {root->left, rest} );
        }
        return false;
    }
};
/*
时间：8ms，击败：93.80%
内存：20.8MB，击败：9.64%
*/

法二：

广搜。

记录根节点到当前节点的路径之和。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if ( !root ) return false;
        queue< pair<TreeNode*, int> > q;
        q.push( {root, targetSum} );
        while ( q.size() ) {
            auto [root, rest] = q.front();
            q.pop();
            rest -= root->val;
            if ( !root->left && !root->right && !rest ) return true;
            if ( root->left ) q.push( {root->left, rest} );
            if ( root->right ) q.push( {root->right, rest} );
        }
        return false;
    }
};
/*
时间：8ms，击败：93.80%
内存：21MB，击败：5.14%
*/