题目的主要信息：

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

方法一：

采用递归。首先判断当前结点是否为NULL，如果是NULL，说明这一条路径不满足条件；否则，sum中减去当前结点的值，如果sum变成了0，且当前结点是叶子结点，说明找到了一条路径。如果sum不为0，则在左右子树递归查找。 具体做法：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root){//root为NULL结束递归
            return false;
        }
        sum -= root->val;//减去当前结点的值
        if(sum == 0 && root->left == NULL && root->right == NULL){//sum=0表示找到了一条路径
            return true;
        }
        return  ( hasPathSum(root->left,sum) || hasPathSum(root->right,sum) );//从左右子树递归查找
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历递归所有的结点。
• 空间复杂度：$O(n)O(n)$，递归栈大小为n。

方法二：

利用栈。用栈模拟递归的过程，首先判断root结点是否为NULL，如果是NULL，返回false；否则，将root结点入栈。遍历栈顶元素，如果结点是叶子结点且路径和为sum，说明找到了一条路径。否则，将左右结点入栈，继续查找。

具体做法：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL){//如果root为NULL，返回false
            return false;
        }
        stack<pair<TreeNode*, int> > stk;//用于保存路径
        stk.push({root, root->val}); //根结点入栈
        while(!stk.empty()){//当栈不为空时
            pair<TreeNode*, int> temp = stk.top();//栈顶元素出栈
            stk.pop();
            if(temp.first->left == NULL && temp.first->right == NULL && temp.second == sum){ //如果栈顶元素为叶子结点，且该路径之和为sum
                return true;
            }
            //否则继续往下扩展路径
            if(temp.first->left != NULL){ //从左结点开始找路径
                int s = temp.second + temp.first->left->val;//以左结点终止的路径和长度
                stk.push({temp.first->left, s});
            }
            if(temp.first->right != NULL){ //右结点继续查找
                int s = temp.second + temp.first->right->val;//以右结点终止的路径和长度
                stk.push({temp.first->right, s});
            }
        }
        return false;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历所有的结点。
• 空间复杂度：$O(n)O(n)$，栈大小为n。