外贸网站建设公司报价,jsp网站建设技术案例,如何申请一个网站 新网,郑州高端网站定制建设给定一个二叉树的 根节点 root#xff0c;请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3]
输出: 1示例 2: 输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7 思路
本题要找出树的最后一行的最左边的值。此时大家应该想…给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3]
输出: 1示例 2: 输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7 思路
本题要找出树的最后一行的最左边的值。此时大家应该想起用层序遍历是非常简单的了反而用递归的话会比较难一点。
我们依然还是先介绍递归法。
#递归
咋眼一看这道题目用递归的话就就一直向左遍历最后一个就是答案呗
没有这么简单一直向左遍历到最后一个它未必是最后一行啊。
我们来分析一下题目在树的最后一行找到最左边的值。
首先要是最后一行然后是最左边的值。
如果使用递归法如何判断是最后一行呢其实就是深度最大的叶子节点一定是最后一行。
如果对二叉树深度和高度还有点疑惑的话请看110.平衡二叉树 (opens new window)。
所以要找深度最大的叶子节点。
那么如何找最左边的呢可以使用前序遍历当然中序后序都可以因为本题没有 中间节点的处理逻辑只要左优先就行保证优先左边搜索然后记录深度最大的叶子节点此时就是树的最后一行最左边的值。
递归三部曲
确定递归函数的参数和返回值
参数必须有要遍历的树的根节点还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了所以递归函数的返回类型为void。
本题还需要类里的两个全局变量maxLen用来记录最大深度result记录最大深度最左节点的数值。
代码如下
int maxDepth INT_MIN; // 全局变量 记录最大深度
int result; // 全局变量 最大深度最左节点的数值
void traversal(TreeNode* root, int depth)确定终止条件
当遇到叶子节点的时候就需要统计一下最大的深度了所以需要遇到叶子节点来更新最大深度。
代码如下
if (root-left NULL root-right NULL) {if (depth maxDepth) {maxDepth depth; // 更新最大深度result root-val; // 最大深度最左面的数值}return;
}确定单层递归的逻辑
在找最大深度的时候递归的过程中依然要使用回溯代码如下 // 中
if (root-left) { // 左depth; // 深度加一traversal(root-left, depth);depth--; // 回溯深度减一
}
if (root-right) { // 右depth; // 深度加一traversal(root-right, depth);depth--; // 回溯深度减一
}
return;完整代码如下
class Solution {
public:int maxDepth INT_MIN;int result;void traversal(TreeNode* root, int depth) {if (root-left NULL root-right NULL) {if (depth maxDepth) {maxDepth depth;result root-val;}return;}if (root-left) {depth;traversal(root-left, depth);depth--; // 回溯}if (root-right) {depth;traversal(root-right, depth);depth--; // 回溯}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};当然回溯的地方可以精简精简代码如下
class Solution {
public:int maxDepth INT_MIN;int result;void traversal(TreeNode* root, int depth) {if (root-left NULL root-right NULL) {if (depth maxDepth) {maxDepth depth;result root-val;}return;}if (root-left) {traversal(root-left, depth 1); // 隐藏着回溯}if (root-right) {traversal(root-right, depth 1); // 隐藏着回溯}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};如果对回溯部分精简的代码 不理解的话可以看这篇257. 二叉树的所有路径(opens new window)
#迭代法
本题使用层序遍历再合适不过了比递归要好理解得多
只需要记录最后一行第一个节点的数值就可以了。
如果对层序遍历不了解看这篇二叉树层序遍历登场 (opens new window)这篇里也给出了层序遍历的模板稍作修改就一过刷了这道题了。
代码如下
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);int result 0;while (!que.empty()) {int size que.size();for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (i 0) result node-val; // 记录最后一行第一个元素if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return result;}
};#总结
本题涉及如下几点
递归求深度的写法我们在110.平衡二叉树 (opens new window)中详细的分析了深度应该怎么求高度应该怎么求。递归中其实隐藏了回溯在257. 二叉树的所有路径 (opens new window)中讲解了究竟哪里使用了回溯哪里隐藏了回溯。层次遍历在二叉树层序遍历登场 (opens new window)深度讲解了二叉树层次遍历。 所以本题涉及到的点我们之前都讲解过这些知识点需要同学们灵活运用这样就举一反三了。
