题目

题解

二叉树结构如下：

1
2
3
4
5
6
7
//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

1. 递归法

  • 时间复杂度: 最坏情况$O(N)$
  • 空间复杂度: 最坏情况$O(N)$
1
2
3
4
5
6
7
8
9
10
 //这道题也是遍历整个树，找符合题意的路径，若没有就返回false
class Solution {//两种方法。1.递归法
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;//若该节点为空，说明该路径所有节点之和未达到要求，返回false
        if(!root->left && !root->right && root->val == sum) return true;//若路径之和等于sum，返回true
        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
        //对左右子树递归
    }
};

2. 队列迭代法（BFS宽度优先搜索）

  • 时间复杂度: 最坏情况$O(N)$
  • 空间复杂度: 最坏情况$O(N)$,这个比DFS慢一点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//这道题也是遍历整个树，找符合题意的路径，若没有就返回false
class Solution {//两种方法。2.队列迭代法（这个方法会改变每个节点的数值，
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;//特殊情况
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){//当q不为空时继续迭代
            auto cur = q.front();q.pop();//建立指针指向当前迭代的值
            if(!cur->left && !cur->right && cur->val == sum) return true;
            //若为叶节点,且叠加的叶节点值为sum，返回ture
            if(cur->left){
                cur->left->val += cur->val;
                q.push(cur->left);
            }//左子节点加入父节点的值，并压入队列
            if(cur->right){
                cur->right->val += cur->val;
                q.push(cur->right);
            }//右子节点同上
        }
        return false;//若未返回true，则全部遍历完成后返回false
    }
};

3. 栈迭代法（DFS深度优先搜索）

这个写法和遍历的写法不太一样，要注意区分！

  • 时间复杂度: 最坏情况$O(N)$
  • 空间复杂度: 当树不平衡的最坏情况下是 $O(N)$ 。在最好情况（树是平衡的）下是 $O(\log N)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {//两种方法。3.栈迭代法，这是DFS（这个方法会改变每个节点的数值，
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;//特殊情况
        stack <TreeNode*> s;
        s.push(root);
        while(!s.empty()){//当s不为空时继续迭代
            auto cur = s.top();s.pop();//建立指针指向当前迭代的值
            if(!cur->left && !cur->right && cur->val == sum) return true;
            //若为叶节点,且叠加的叶节点值为sum，返回ture
            if(cur->left){
                cur->left->val += cur->val;
                s.push(cur->left);
            }//左子节点加入父节点的值，并压入栈
            if(cur->right){
                cur->right->val += cur->val;
                s.push(cur->right);
            }//右子节点同上
        }
        return false;//若未返回true，则全部遍历完成后返回false
    }
};