112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

2.示例

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
1
2
3

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
1
2
3

3.答案

①递归

注意第二个示例，当结点为空时认为不存在路径返回false;
可以使得参数 targetSum等于当前路径上为了凑出targetSum还差的数值。

停止条件:
结点为空时返回false, 当前结点为叶子结点且val=targetSum(刚好凑出targetSum) 返回true。
递归内容: 在左孩子上查找，在右孩子上查找
返回值: 左右孩子查找结果的或

 bool hasPathSum(TreeNode* root, int targetSum) {  
        //尝试递归，将taargetsum看做还差的值
        if(!root) return false;//空指针,检查路径时，不能把节点为空当做一种
        if(!root->left&&!root->right) return targetSum==root->val;  //叶子结点，把这个当做递归的退出条件之一
         return hasPathSum(root->left,targetSum-root->val)||hasPathSum(root->right,targetSum-root->val);
1
2
3
4
5

②BFS

层次遍历中，可以一层一层检查，每次保存当前结点和当前路径所有节点和.

 bool hasPathSum(TreeNode* root, int targetSum) { 
        if(!root) return false;//空指针,检查路径时，不能把节点为空当做一种
        queue<TreeNode*> qt;
        queue<int> qi;
        qt.push(root); 
        qi.push(root->val);
        while(!qt.empty()){ 
            TreeNode* tmp=qt.front();  //取出当前结点
            qt.pop();
            int val=qi.front();  //当前路径和
            qi.pop();  

            if(!tmp->left&&!tmp->right) {   //当前为叶子结点
                if(targetSum==val) return true;
                continue;
            }

            if(tmp->left) qt.push(tmp->left),qi.push(val+tmp->left->val);
            if(tmp->right) qt.push(tmp->right),qi.push(val+tmp->right->val);
        }
        return false;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

③DFS

深度优先遍历同样，每次保存当前结点和当前结点路径和。

 bool hasPathSum(TreeNode* root, int targetSum) { 
		 if(!root) return false;
        /深度优先  ,每次都是一条路径和
        stack<TreeNode*> st;
        stack<int> si;
        st.push(root); 
        si.push(root->val);
        while(!st.empty()){ 
            TreeNode* tmp=st.top();  //取出当前结点
            st.pop();
            int val=si.top();
            si.pop();  

            if(!tmp->left&&!tmp->right) {   //当前为叶子结点
                if(targetSum==val) return true;
                continue;
            }

            if(tmp->left) st.push(tmp->left),si.push(val+tmp->left->val);
            if(tmp->right) st.push(tmp->right),si.push(val+tmp->right->val);
        }
        return false;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/path-sum