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

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

主要学习内容：

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

2.to_string函数的使用

513.找树左下角的值

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

解法一：回溯

思路：

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

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

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

深度最深才能是最下面的

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

1.函数参数和返回值

int res;
int curdepth=0;
void tra(TreeNode *t,int depth)

res记录结果

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

depth为当前结点的深度

2.终止条件

if(t->left==nullptr&&t->right==nullptr)
{if(depth>curdepth){res=t->val;curdepth=depth;}return;
}

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

3.本层代码逻辑

if(t->left)tra(t->left,depth+1);
if(t->right)tra(t->right,depth+1);

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

//不省略回溯的版本
if(t->left)
{depth++;tra(t->left,depth);depth--;
}
if(t->right)
{depth++;tra(t->right,depth);depth--;
}

4.完整代码

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;}
};

解法二：层序遍历

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

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

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;}};

112.路径总和

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

解法：回溯

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

1.函数参数和返回值

bool flag=false;
void tra(TreeNode *t,int target)

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

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

2.终止条件

if(t->left==nullptr&&t->right==nullptr)
{if(target==0)flag=true;
}

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

3.本层代码逻辑

易错

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

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

if(t->left)tra(t->left,target-t->left->val);
if(t->right)tra(t->right,target-t->right->val);

完整代码：

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;}
};