欢迎大家参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!
给定一个二叉树,在树的最后一行找到最左边的值。
示例 1:
示例 2:
本地要找出树的最后一行找到最左边的值。此时大家应该想起用层序遍历是非常简单的了,反而用递归的话会比较难一点。
我们依然还是先介绍递归法。
咋眼一看,这道题目用递归的话就就一直向左遍历,最后一个就是答案呗?
没有这么简单,一直向左遍历到最后一个,它未必是最后一行啊。
我们来分析一下题目:在树的最后一行找到最左边的值。
首先要是最后一行,然后是最左边的值。
如果使用递归法,如何判断是最后一行呢,其实就是深度最大的叶子节点一定是最后一行。
如果对二叉树深度和高度还有点疑惑的话,请看:二叉树:我平衡么?。
所以要找深度最大的叶子节点。
那么如果找最左边的呢?可以使用前序遍历,这样才先优先左边搜索,然后记录深度最大的叶子节点,此时就是树的最后一行最左边的值。
递归三部曲:
- 确定递归函数的参数和返回值
参数必须有要遍历的树的根节点,还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了,所以递归函数的返回类型为void。
本题还需要类里的两个全局变量,maxLen用来记录最大深度,maxleftValue记录最大深度最左节点的数值。
代码如下:
int maxLen = INT_MIN; // 全局变量 记录最大深度
int maxleftValue; // 全局变量 最大深度最左节点的数值
void traversal(TreeNode* root, int leftLen)
有的同学可能疑惑,为啥不能递归函数的返回值返回最长深度呢?
其实很多同学都对递归函数什么时候要有返回值,什么时候不能有返回值很迷茫。
如果需要遍历整颗树,递归函数就不能有返回值。如果需要遍历某一条固定路线,递归函数就一定要有返回值!
初学者可能对这个结论不太理解,别急,后面我会安排一道题目专门讲递归函数的返回值问题。这里大家暂时先了解一下。
本题我们是要遍历整个树找到最深的叶子节点,需要遍历整颗树,所以递归函数没有返回值。
- 确定终止条件
当遇到叶子节点的时候,就需要统计一下最大的深度了,所以需要遇到叶子节点来更新最大深度。
代码如下:
if (root->left == NULL && root->right == NULL) {
if (leftLen > maxLen) {
maxLen = leftLen; // 更新最大深度
maxleftValue = root->val; // 最大深度最左面的数值
}
return;
}
- 确定单层递归的逻辑
在找最大深度的时候,递归的过程中依然要使用回溯,代码如下:
// 中
if (root->left) { // 左
leftLen++; // 深度加一
traversal(root->left, leftLen);
leftLen--; // 回溯,深度减一
}
if (root->right) { // 右
leftLen++; // 深度加一
traversal(root->right, leftLen);
leftLen--; // 回溯,深度减一
}
return;
完整代码如下:
class Solution {
public:
int maxLen = INT_MIN;
int maxleftValue;
void traversal(TreeNode* root, int leftLen) {
if (root->left == NULL && root->right == NULL) {
if (leftLen > maxLen) {
maxLen = leftLen;
maxleftValue = root->val;
}
return;
}
if (root->left) {
leftLen++;
traversal(root->left, leftLen);
leftLen--; // 回溯
}
if (root->right) {
leftLen++;
traversal(root->right, leftLen);
leftLen--; // 回溯
}
return;
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);
return maxleftValue;
}
};
当然回溯的地方可以精简,精简代码如下:
class Solution {
public:
int maxLen = INT_MIN;
int maxleftValue;
void traversal(TreeNode* root, int leftLen) {
if (root->left == NULL && root->right == NULL) {
if (leftLen > maxLen) {
maxLen = leftLen;
maxleftValue = root->val;
}
return;
}
if (root->left) {
traversal(root->left, leftLen + 1); // 隐藏着回溯
}
if (root->right) {
traversal(root->right, leftLen + 1); // 隐藏着回溯
}
return;
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);
return maxleftValue;
}
};
如果对回溯部分精简的代码 不理解的话,可以看这篇二叉树:找我的所有路径?和二叉树:以为使用了递归,其实还隐藏着回溯 。这两篇文章详细分析了回溯隐藏在了哪里。
本题使用层序遍历再合适不过了,比递归要好理解的多!
只需要记录最后一行第一个节点的数值就可以了。
如果对层序遍历不了解,看这篇二叉树:层序遍历登场!,这篇里也给出了层序遍历的模板,稍作修改就一过刷了这道题了。
代码如下:
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> 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;
}
};
本题涉及如下几点:
- 递归求深度的写法,我们在二叉树:我平衡么?中详细的分析了深度应该怎么求,高度应该怎么求。
- 递归中其实隐藏了回溯,在二叉树:以为使用了递归,其实还隐藏着回溯中讲解了究竟哪里使用了回溯,哪里隐藏了回溯。
- 层次遍历,在二叉树:层序遍历登场!深度讲解了二叉树层次遍历。 所以本题涉及到的点,我们之前都讲解过,这些知识点需要同学们灵活运用,这样就举一反三了。
Java:
// 递归法
class Solution {
private int Deep = -1;
private int value = 0;
public int findBottomLeftValue(TreeNode root) {
value = root.val;
findLeftValue(root,0);
return value;
}
private void findLeftValue (TreeNode root,int deep) {
if (root == null) return;
if (root.left == null && root.right == null) {
if (deep > Deep) {
value = root.val;
Deep = deep;
}
}
if (root.left != null) findLeftValue(root.left,deep + 1);
if (root.right != null) findLeftValue(root.right,deep + 1);
}
}
//迭代法
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int res = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode poll = queue.poll();
if (i == 0) {
res = poll.val;
}
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
}
}
return res;
}
}
Python:
//递归法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findBottomLeftValue(self, root: TreeNode) -> int:
depth=0
self.res=[]
def level(root,depth):
if not root:return
if depth==len(self.res):
self.res.append([])
self.res[depth].append(root.val)
level(root.left,depth+1)
level(root.right,depth+1)
level(root,depth)
return self.res[-1][0]
Go:
递归法
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var maxDeep int // 全局变量 深度
var value int //全局变量 最终值
func findBottomLeftValue(root *TreeNode) int {
if root.Left==nil&&root.Right==nil{//需要提前判断一下(不要这个if的话提交结果会出错,但执行代码不会。防止这种情况出现,故先判断是否只有一个节点)
return root.Val
}
findLeftValue (root,maxDeep)
return value
}
func findLeftValue (root *TreeNode,deep int){
//最左边的值在左边
if root.Left==nil&&root.Right==nil{
if deep>maxDeep{
value=root.Val
maxDeep=deep
}
}
//递归
if root.Left!=nil{
deep++
findLeftValue(root.Left,deep)
deep--//回溯
}
if root.Right!=nil{
deep++
findLeftValue(root.Right,deep)
deep--//回溯
}
}
迭代法
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findBottomLeftValue(root *TreeNode) int {
queue:=list.New()
var gradation int
queue.PushBack(root)
for queue.Len()>0{
length:=queue.Len()
for i:=0;i<length;i++{
node:=queue.Remove(queue.Front()).(*TreeNode)
if i==0{gradation=node.Val}
if node.Left!=nil{
queue.PushBack(node.Left)
}
if node.Right!=nil{
queue.PushBack(node.Right)
}
}
}
return gradation
}
JavaScript:
- 递归版本
var findBottomLeftValue = function(root) {
//首先考虑递归遍历 前序遍历 找到最大深度的叶子节点即可
let maxPath = 0,resNode = null;
// 1. 确定递归函数的函数参数
const dfsTree = function(node,curPath){
// 2. 确定递归函数终止条件
if(node.left===null&&node.right===null){
if(curPath>maxPath){
maxPath = curPath;
resNode = node.val;
}
// return ;
}
node.left&&dfsTree(node.left,curPath+1);
node.right&&dfsTree(node.right,curPath+1);
}
dfsTree(root,1);
return resNode;
};
- 层序遍历
var findBottomLeftValue = function(root) {
//考虑层序遍历 记录最后一行的第一个节点
let queue = [];
if(root===null){
return null;
}
queue.push(root);
let resNode;
while(queue.length){
let length = queue.length;
for(let i=0; i<length; i++){
let node = queue.shift();
if(i===0){
resNode = node.val;
}
node.left&&queue.push(node.left);
node.right&&queue.push(node.right);
}
}
return resNode;
};