Day92 | 灵神 | 二叉树 路径总和

112.路径总和

112. 路径总和 - 力扣（LeetCode）

思路：

1.递归函数意义

如果在根节点为t的树中可以找到长度为target的路径就返回true，找不到就返回false

2.参数和返回值

1
bool tra(TreeNode *t,int target)

参数中的target在传入之前会先减掉当前结点的值作为给下一个结点传入的值

如果在根节点为t的树中可以找到长度为target的路径就返回true，找不到就返回false

3.终止条件（边界条件）

如果我们碰到了空节点，那就是false，说明没找到路径

1
2
if(t==nullptr)
	return false;

4.本层逻辑（非边界条件）

减去本层节点值之后判断是否是我们要找的路径

即在叶子结点，并且target也减到0了

然后递归遍历左右子树，不管哪边找到了我们都可以返回true

1
2
3
4
5
6
target-=t->val;
      if(t->left==nullptr&&t->right==nullptr)
          return target==0;
      bool l=tra(t->left,target);
      bool r=tra(t->right,target);
      return l||r;

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    bool tra(TreeNode *t,int target)
    {
        if(t==nullptr)
            return false; 
        target-=t->val;
        if(t->left==nullptr&&t->right==nullptr)
            return target==0;
        bool l=tra(t->left,target);
        bool r=tra(t->right,target);
        return l||r;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        return tra(root,targetSum);
    }
};



/*
class Solution {
public:
    bool flag=false;
    void tra(TreeNode *t,int target)
    {
        if(t==nullptr)
            return;
        target-=t->val;
        if(t->left==nullptr&&t->right==nullptr&&target==0)
            flag=true;
        tra(t->left,target);
        tra(t->right,target);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        tra(root,targetSum);
        return flag;
    }
};*/