题解 | #二叉树中是否存在节点和为指定值的路径#

递归方法

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        if(!root)
            return false;
        stack<TreeNode*> Stack;
        TreeNode* tmp = root;
        Stack.push(tmp);
        if(!tmp->left && !tmp->right && sum == tmp->val)
            return true;
        return hasPathSum(root->right, sum-tmp->val) || hasPathSum(root->left, sum-tmp->val);
    }
};

非递归方法

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

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;
        }
        //首先对树进行前序遍历，会用到栈
        TreeNode* tmp = root;
        stack<TreeNode*> Stack;
        int cal_sum = 0;
        Stack.push(tmp);//根节点入栈
        while(Stack.size()>0)//cal_sum != sum )//栈不为空
        {
            TreeNode* node = Stack.top();
            Stack.pop();

            if(!node->left && !node->right)
            {
                cal_sum = node->val;
                if(cal_sum == sum)
                    return true;
            }
            if(node->right)
            {
                node->right->val = node->val + node->right->val;
                Stack.push(node->right);
            }
            if(node->left)
            {
                node->left->val = node->val + node->left->val;
                Stack.push(node->left);
            }
        }
        return false;
    }
};