题目的主要信息：

• 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径
• 路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
• 路径只能从父节点到子节点，不能从子节点到父节点
• 要求：空间复杂度 $O(n)O(n)$，时间复杂度 $O(n)O(n)$

方法一：递归

具体做法：

可以使用递归先序遍历，每次检查遍历到的结点是否为叶子结点，且当前sum值等于结点值，如果可以则返回true；如果不行，则检查左右子节点是否可以有完成路径的，如果任意一条路径可以都返回true，因此这里选用两个子节点递归的或。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL) //空结点找不到路径
            return false;
        if(root->left == NULL && root->right == NULL && sum - root->val == 0) //叶子结点，且路径和为sum
            return true;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); //递归进入子结点
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，先序遍历二叉树所有结点
• 空间复杂度：$O(n)O(n)$，最坏情况二叉树化为链表，递归栈空间最大为$nn$

方法二：非递归

具体做法：

也可以使用栈辅助，进行dfs遍历，检查往下的路径中是否有等于sum的路径和。

注意，这里仅是dfs，而不是先序遍历，左右节点的顺序没有关系，因为每次往下都是单独添加某个结点的值相加然后继续往下，因此左右节点谁先遍历不管用。

使用栈辅助dfs，同时用pair记录相应到结点为止的路径和。根节点先入栈，然后不断遍历栈中内容，将子节点加入栈中，如果遇到叶子节点且路径和等于目标值，则说明找到。如果全部遍历完都没找到，说明没有。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL) //空结点找不到路径
            return false;
        stack<pair<TreeNode*, int> > s; //栈辅助深度优先遍历，并记录到相应结点的路径和
        s.push({root, root->val}); //根结点入栈
        while(!s.empty()){
            auto temp = s.top();
            s.pop();
            if(temp.first->left == NULL && temp.first->right == NULL && temp.second == sum) //叶子节点且路径和等于sum
                return true;
            if(temp.first->left != NULL) //左结点入栈
                s.push({temp.first->left, temp.second + temp.first->left->val});
            if(temp.first->right != NULL) //右结点入栈
                s.push({temp.first->right, temp.second + temp.first->right->val});
        }
        return false;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，dfs遍历二叉树所有结点
• 空间复杂度：$O(n)O(n)$，最坏情况二叉树化为链表，递归栈空间最大为$nn$