题目描述

image.png

题解

和二叉树根节点到叶子结点和为指定值的路径思路相同

代码

// hasPathSum.cpp
#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int val){
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
};


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;
        }
        meet = false;
        targetSum = sum;
        sumNumber(root, root->val);
        return meet;
    }
private:
    bool meet;
    int targetSum;
    void sumNumber(TreeNode* t, int sum){
        if (meet){
            return;
        }
        if (t->left == NULL && t->right == NULL){
            if (sum == targetSum){
                meet = true;
            }
            return;
        }
        if (t->left != NULL){
            sumNumber(t->left, t->left->val + sum);
        }
        if (t->right != NULL){
            sumNumber(t->right, t->right->val + sum);
        }
    }
};

int main()
{
    TreeNode* root = new TreeNode(5);
    TreeNode* left = new TreeNode(4);
    TreeNode* right = new TreeNode(8);
    TreeNode* leftleft = new TreeNode(1);
    TreeNode* leftright = new TreeNode(11);
    TreeNode* leftrightleft = new TreeNode(2);
    TreeNode* leftrightright = new TreeNode(7);
    TreeNode* rightright = new TreeNode(9);
    root->left = left;
    root->right = right;
    left->left = leftleft;
    left->right = leftright;
    leftright->left = leftrightleft;
    leftright->right = leftrightright;
    right->right = rightright;

    Solution s;
    cout << s.hasPathSum(root, 22) << endl;
    delete root;
    delete left;
    delete right;
    delete leftleft;
    delete leftright;
    delete leftrightleft;
    delete leftrightright;
    delete rightright;
    return 0;

}