公众号:offer多多
V1
2021/09/25阅读:92主题:橙心
513. 找树左下角的值

思路描述:
-
思路1 :深度优先搜索
-
看到这个题目马上dfs遍历, 但是最左边 节点的值如何寻找呢?不清楚 用vector 表示没一层记录?还是定义2个变量表示。 -
观察 左边不一定是left的left。 题目 右视图,【先顺遍历】这里存储全部元素。 -
简化 题目是每层最 left的。定义2个变量就可以。 -
重点:只访问最left元素。其他元素不访问。 只有i层 大于i-层
-
描述:
-
假设当前层次i层,maxlevel=i,中序遍历(In-Order Traversal) -
当前层次i+1,第一遇到 i+1>maxlevel 命中。 -
然后继续root.right中序遍历 参考: https://leetcode-cn.com/problems/find-bottom-left-tree-value/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-er-ch-w3og/ https://leetcode-cn.com/problems/find-bottom-left-tree-value/solution/di-gui-jian-yi-hua-tu-by-zhouzihong-x2yp/
-
思路2:
只要深度优先松搜索实现的代码,广度也可以。 这里同样问题。每一层第一个,就是最left。
-
描述:
-
定义队列; -
遍历队列:队列同时存在i ,i+1层元素。 统计当前层的个数 -
第一个就是当前层次的。 4.重复 步骤2和3.
回顾:o(n)
题目--右视图--左视图--叶子节点的左视图---定义2该个变量 --优化 前序遍历改为-->中序遍历
代码
-
思路1
class Solution1
{
public:
//思路1 :深度优先搜索:中序遍历(In-Order Traversal)
//特点:回溯时候在访问该元素。
//https://zh.wikipedia.org/wiki/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86
int findBottomLeftValue(TreeNode *root)
{
int maxlevel = -1;
int leftValue = 0;
int curlevel = 0;
dfs(root, curlevel, maxlevel, leftValue);
return leftValue;
}
//元素比较:每层最left
void dfs(TreeNode *root, int curlevel, int &maxlevel, int &left)
{
if (nullptr == root)
{
return; //结束条件 必备
}
if (root->left)
{ //减少一层递归
dfs(root->left, curlevel + 1, maxlevel, left);
}
//优化:裁剪
//其他遍历方式可以吗?可以
//这里上来设置maxlevel=3。小于3的不需要设置
if (curlevel > maxlevel)
{
maxlevel = curlevel;
left = root->val;
}
if (root->right)
{ //减少一层递归
dfs(root->right, curlevel + 1, maxlevel, left);
}
}
}
-
思路2
class Solution
{
public:
int findBottomLeftValue(TreeNode *root)
{
int output = 0;
queue<TreeNode*> myqueue;
myqueue.push(root); //循环条件
while (!myqueue.empty())
{
int len = myqueue.size();
for (int i = 0; i < len; i++)
{
TreeNode *ptemp = myqueue.front();
myqueue.pop();
if (i == 0)
{
output = ptemp->val;
//每层第一个元素
}
if (ptemp->left)
{
myqueue.push(ptemp->left);
}
if (ptemp->right)
{
myqueue.push(ptemp->right);
}
}
}
return output;
}
};
作者介绍
公众号:offer多多
V1