代码随想录 | Day21 | 二叉树：找树左下角的值&&路径总和

主要学习内容：

1.利用二叉树的谦虚遍历进行题目解答

2.to_string函数的使用

513.找树左下角的值

513. 找树左下角的值 - 力扣（LeetCode）

解法一：回溯

思路：

难突破的点是我们怎么知道我们找的叶子结点是最左边的

其实只需要一直往下遍历，每一层最先遍历到的肯定是左边的

那如何知道是最下面的呢？

深度最深才能是最下面的

所以我们的目标就是找深度最深的叶子结点，保存第一个遍历到的深度最深的结点。这就是我们的答案

1.函数参数和返回值

1
2
3
4
int res;
int curdepth=0;
void tra(TreeNode *t,int depth)
123

res记录结果

curdepth用于更新当前的最大深度

depth为当前结点的深度

2.终止条件

1
2
3
4
5
6
7
8
9
10
11
if(t->left==nullptr&&t->right==nullptr)
{
	if(depth>curdepth)
	{
		res=t->val;
		curdepth=depth;
	}
                
	return;
}
12345678910

遍历到叶子结点并且当前叶子结点深度最深，就是我们要的答案，保存后再更新一下当前最大深度，用于找更下层的结点

3.本层代码逻辑

1
2
3
4
5
if(t->left)
	tra(t->left,depth+1);
if(t->right)
	tra(t->right,depth+1);
1234

在上面更新完结果后，继续遍历左右子树，+1是每层遍历深度+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//不省略回溯的版本
if(t->left)
{
    depth++;
    tra(t->left,depth);
    depth--;
}
if(t->right)
{
    depth++;
    tra(t->right,depth);
    depth--;
}
12345678910111213

4.完整代码

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
class Solution {
public:
    vector<string> res;
    void tra(string s,TreeNode *t)
    {
        if(t==nullptr)
            return;
        if(t->left==nullptr&&t->right==nullptr)
        {
            s+=to_string(t->val);
            res.push_back(s);
            return;
        }
        s+=to_string(t->val);
        s+="->";
        tra(s,t->left);
        tra(s,t->right);
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        string s;
        tra(s,root);
        return res;
    }
};
123456789101112131415161718192021222324

解法二：层序遍历

我们每层第一个元素就是最左边的元素，每次都更新一下，到最后一层也会更新

只需要在模板的基础上再把每层第一个元素更新一下就行（不清楚模板可以翻看前面的层序遍历相关）

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
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode *> q;
        q.push(root);
        int res;
        while(!q.empty())
        {
            int size=q.size();
            res=q.front()->val;//更新
            for(int i=0;i<size;i++)
            {
                TreeNode *t=q.front();
                q.pop();
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
        }
        return res;
    }

};
123456789101112131415161718192021222324

112.路径总和

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

解法：回溯

一个经典的树的路径问题，可以刷完回溯算法后再回来看

1.函数参数和返回值

1
2
3
bool flag=false;
void tra(TreeNode *t,int target)
12

flag是标记是否成功，找到就为ture

target是用来减的，减到0就说明找到了答案，利用一个反向思维吧算是

2.终止条件

1
2
3
4
5
6
if(t->left==nullptr&&t->right==nullptr)
{
	if(target==0)
	flag=true;
}
12345

是叶子结点且已经减到了0，那么就是答案，标记为true

3.本层代码逻辑

易错

减去的是t的子树的val而不是t本身的val

调用的时候就要减去，这样方便终止条件进行比较，不然进入本层调用函数以后还要现场加或者减容易搞混

1
2
3
4
5
if(t->left)
	tra(t->left,target-t->left->val);
if(t->right)
	tra(t->right,target-t->right->val);
1234

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool flag=false;
    void tra(TreeNode *t,int target)
    {
        if(t->left==nullptr&&t->right==nullptr)
        {
            if(target==0)
                flag=true;
        }
        if(t->left)
            tra(t->left,target-t->left->val);
        if(t->right)
            tra(t->right,target-t->right->val);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root==nullptr)
            return false;
        tra(root,targetSum-root->val);
        return flag;
    }
};