Leetcode 112. 路径总和

题目

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

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

思路

• 使用先序遍历的方法
• 确定递归函数的参数和返回值：二叉树的根节点和一个计数器，计数器用来计算二叉树的一条路径上的节点是否等于目标值
• 确定终止条件：将计数器初始化为目标值，每次遍历一个节点，就减去节点值，如果当前节点是叶子节点并且count = 0,说明找到了这样的路径。如果找到了叶子节点但是count != 0,说明该条路径不符合，准备回溯。
• 单层递归逻辑：递归遍历左子树，递归遍历右子树，首先count减去节点的值，如果不行，直接回退节点值。

代码

/** * 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 traversakl(TreeNode* cur,int count)
    {
    
        // 遇到叶子节点并且count = 0
        if(!cur->left && !cur->right && count == 0)
        {
    
            return true;// 递归出口
        }

        if(!cur->left && !cur->right)
        {
    
            // 遇到叶子节点 并且count != 0 说明该条路径不符合
            return false;// 递归出口
        }

        if(cur->left != NULL)
        {
    
            count -= cur->left->val;// 递归左子树
            if(traversakl(cur->left,count))
            {
    
                return true;
            }
            count += cur->left->val;// 回溯 撤销处理结果
        }

        if(cur->right != NULL)
        {
    
            count -= cur->right->val;
            if(traversakl(cur->right,count))
            {
    
                return true;
            }
            count += cur->right->val;
        }

        return false;
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
    
        if(root == NULL)
        {
    
            return false;
        }

        return traversakl(root,targetSum - root->val);
    }
};