跳转至

112.路径总和 (Easy)*

题目描述*

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

示例*

给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

代码*

简单的递归，栈模拟迭代。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == nullptr) {
            return false;
        }
        if(root->left == nullptr && root->right == nullptr && root->val == sum) {
            return true;
        }
        if(root->left != nullptr && hasPathSum(root->left, sum - root->val)) {
            return true;
        }
        if(root->right != nullptr && hasPathSum(root->right, sum - root->val)) {
            return true;
        }
        return false;
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == nullptr) {
            return false;
        }
        stack<TreeNode*> helpStack;
        stack<int> sumStack;
        TreeNode *cur = root;
        int curSum = 0;
        while(cur != nullptr || !helpStack.empty()) {
            while(cur != nullptr) {
                helpStack.push(cur);
                curSum += cur->val;
                sumStack.push(curSum);
                cur = cur->left;
            }
            cur = helpStack.top();
            helpStack.pop();
            curSum = sumStack.top();
            sumStack.pop();
            if(curSum == sum && cur->left == nullptr && cur->right == nullptr) {
                return true;
            }
            cur = cur->right;
        }
        return false;
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == nullptr) {
            return false;
        }
        queue<TreeNode*> helpQueue;
        queue<int> sumQueue;
        helpQueue.push(root);
        sumQueue.push(root->val);
        TreeNode *cur = root;
        int curSum = 0;
        while(!helpQueue.empty()) {
            int depth = helpQueue.size();
            for(int i = 0; i < depth; i++) {
                cur = helpQueue.front();
                helpQueue.pop();
                curSum = sumQueue.front();
                sumQueue.pop();
                if(cur != nullptr) {
                    if(cur->left == nullptr && cur->right == nullptr && curSum == sum) {
                        return true;
                    }
                    if(cur->left != nullptr) {
                        helpQueue.push(cur->left);
                        sumQueue.push(curSum + cur->left->val);
                    }
                    if(cur->right != nullptr) {
                        helpQueue.push(cur->right);
                        sumQueue.push(curSum + cur->right->val);
                    }
                }
            }
        }
        return false;
    }
};
最后更新: July 23, 2022