参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!
给定一个二叉树,在树的最后一行找到最左边的值。
示例 1:
示例 2:
《代码随想录》算法视频公开课:怎么找二叉树的左下角? 递归中又带回溯了,怎么办?| LeetCode:513.找二叉树左下角的值,相信结合视频在看本篇题解,更有助于大家对本题的理解。
本题要找出树的最后一行的最左边的值。此时大家应该想起用层序遍历是非常简单的了,反而用递归的话会比较难一点。
我们依然还是先介绍递归法。
咋眼一看,这道题目用递归的话就就一直向左遍历,最后一个就是答案呗?
没有这么简单,一直向左遍历到最后一个,它未必是最后一行啊。
我们来分析一下题目:在树的最后一行找到最左边的值。
首先要是最后一行,然后是最左边的值。
如果使用递归法,如何判断是最后一行呢,其实就是深度最大的叶子节点一定是最后一行。
如果对二叉树深度和高度还有点疑惑的话,请看:110.平衡二叉树。
所以要找深度最大的叶子节点。
那么如何找最左边的呢?可以使用前序遍历(当然中序,后序都可以,因为本题没有 中间节点的处理逻辑,只要左优先就行),保证优先左边搜索,然后记录深度最大的叶子节点,此时就是树的最后一行最左边的值。
递归三部曲:
- 确定递归函数的参数和返回值
参数必须有要遍历的树的根节点,还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了,所以递归函数的返回类型为void。
本题还需要类里的两个全局变量,maxDepth用来记录最大深度,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. 二叉树的所有路径
本题使用层序遍历再合适不过了,比递归要好理解得多!
只需要记录最后一行第一个节点的数值就可以了。
如果对层序遍历不了解,看这篇二叉树:层序遍历登场!,这篇里也给出了层序遍历的模板,稍作修改就一过刷了这道题了。
代码如下:
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;
}
};
本题涉及如下几点:
- 递归求深度的写法,我们在110.平衡二叉树中详细的分析了深度应该怎么求,高度应该怎么求。
- 递归中其实隐藏了回溯,在257. 二叉树的所有路径中讲解了究竟哪里使用了回溯,哪里隐藏了回溯。
- 层次遍历,在二叉树:层序遍历登场!深度讲解了二叉树层次遍历。 所以本题涉及到的点,我们之前都讲解过,这些知识点需要同学们灵活运用,这样就举一反三了。
// 递归法
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;
}
}
(版本一)递归法 + 回溯
class Solution:
def findBottomLeftValue(self, root: TreeNode) -> int:
self.max_depth = float('-inf')
self.result = None
self.traversal(root, 0)
return self.result
def traversal(self, node, depth):
if not node.left and not node.right:
if depth > self.max_depth:
self.max_depth = depth
self.result = node.val
return
if node.left:
depth += 1
self.traversal(node.left, depth)
depth -= 1
if node.right:
depth += 1
self.traversal(node.right, depth)
depth -= 1
(版本二)递归法+精简
class Solution:
def findBottomLeftValue(self, root: TreeNode) -> int:
self.max_depth = float('-inf')
self.result = None
self.traversal(root, 0)
return self.result
def traversal(self, node, depth):
if not node.left and not node.right:
if depth > self.max_depth:
self.max_depth = depth
self.result = node.val
return
if node.left:
self.traversal(node.left, depth+1)
if node.right:
self.traversal(node.right, depth+1)
(版本三) 迭代法
# 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
from collections import deque
class Solution:
def findBottomLeftValue(self, root):
if root is None:
return 0
queue = deque()
queue.append(root)
result = 0
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
if i == 0:
result = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
递归法:
var depth int // 全局变量 最大深度
var res int // 记录最终结果
func findBottomLeftValue(root *TreeNode) int {
depth, res = 0, 0 // 初始化
dfs(root, 1)
return res
}
func dfs(root *TreeNode, d int) {
if root == nil {
return
}
// 因为先遍历左边,所以左边如果有值,右边的同层不会更新结果
if root.Left == nil && root.Right == nil && depth < d {
depth = d
res = root.Val
}
dfs(root.Left, d+1) // 隐藏回溯
dfs(root.Right, d+1)
}
迭代法:
func findBottomLeftValue(root *TreeNode) int {
var gradation int
queue := list.New()
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
}
递归版本:
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;
}
}
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;
};
递归法:
function findBottomLeftValue(root: TreeNode | null): number {
function recur(root: TreeNode, depth: number): void {
if (root.left === null && root.right === null) {
if (depth > maxDepth) {
maxDepth = depth;
resVal = root.val;
}
return;
}
if (root.left !== null) recur(root.left, depth + 1);
if (root.right !== null) recur(root.right, depth + 1);
}
let maxDepth: number = 0;
let resVal: number = 0;
if (root === null) return resVal;
recur(root, 1);
return resVal;
};
迭代法:
function findBottomLeftValue(root: TreeNode | null): number {
let helperQueue: TreeNode[] = [];
if (root !== null) helperQueue.push(root);
let resVal: number = 0;
let tempNode: TreeNode;
while (helperQueue.length > 0) {
resVal = helperQueue[0].val;
for (let i = 0, length = helperQueue.length; i < length; i++) {
tempNode = helperQueue.shift()!;
if (tempNode.left !== null) helperQueue.push(tempNode.left);
if (tempNode.right !== null) helperQueue.push(tempNode.right);
}
}
return resVal;
};
递归版本:
var maxLen = -1
var maxLeftValue = 0
func findBottomLeftValue_2(_ root: TreeNode?) -> Int {
traversal(root, 0)
return maxLeftValue
}
func traversal(_ root: TreeNode?, _ deep: Int) {
guard let root = root else {
return
}
if root.left == nil && root.right == nil {
if deep > maxLen {
maxLen = deep
maxLeftValue = root.val
}
return
}
if root.left != nil {
traversal(root.left, deep + 1)
}
if root.right != nil {
traversal(root.right, deep + 1)
}
return
}
层序遍历:
func findBottomLeftValue(_ root: TreeNode?) -> Int {
guard let root = root else {
return 0
}
var queue = [root]
var result = 0
while !queue.isEmpty {
let size = queue.count
for i in 0..<size {
let firstNode = queue.removeFirst()
if i == 0 {
result = firstNode.val
}
if let leftNode = firstNode.left {
queue.append(leftNode)
}
if let rightNode = firstNode.right {
queue.append(rightNode)
}
}
}
return result
}
递归版本:
object Solution {
def findBottomLeftValue(root: TreeNode): Int = {
var maxLeftValue = 0
var maxLen = Int.MinValue
// 递归方法
def traversal(node: TreeNode, depth: Int): Unit = {
// 如果左右都为空并且当前深度大于最大深度,记录最左节点的值
if (node.left == null && node.right == null && depth > maxLen) {
maxLen = depth
maxLeftValue = node.value
}
if (node.left != null) traversal(node.left, depth + 1)
if (node.right != null) traversal(node.right, depth + 1)
}
traversal(root, 0) // 调用方法
maxLeftValue // return关键字可以省略
}
}
层序遍历:
import scala.collection.mutable
def findBottomLeftValue(root: TreeNode): Int = {
val queue = mutable.Queue[TreeNode]()
queue.enqueue(root)
var res = 0 // 记录每层最左侧结果
while (!queue.isEmpty) {
val len = queue.size
for (i <- 0 until len) {
val curNode = queue.dequeue()
if (i == 0) res = curNode.value // 记录最最左侧的节点
if (curNode.left != null) queue.enqueue(curNode.left)
if (curNode.right != null) queue.enqueue(curNode.right)
}
}
res // 最终返回结果,return关键字可以省略
}
层序遍历
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut queue = VecDeque::new();
let mut res = 0;
if root.is_some() {
queue.push_back(root);
}
while !queue.is_empty() {
for i in 0..queue.len() {
let node = queue.pop_front().unwrap().unwrap();
if i == 0 {
res = node.borrow().val;
}
if node.borrow().left.is_some() {
queue.push_back(node.borrow().left.clone());
}
if node.borrow().right.is_some() {
queue.push_back(node.borrow().right.clone());
}
}
}
res
}
}
递归
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
//*递归*/
pub fn find_bottom_left_value(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut res = 0;
let mut max_depth = i32::MIN;
Self::traversal(root, 0, &mut max_depth, &mut res);
res
}
fn traversal(
root: Option<Rc<RefCell<TreeNode>>>,
depth: i32,
max_depth: &mut i32,
res: &mut i32,
) {
let node = root.unwrap();
if node.borrow().left.is_none() && node.borrow().right.is_none() {
if depth > *max_depth {
*max_depth = depth;
*res = node.borrow().val;
}
return;
}
if node.borrow().left.is_some() {
Self::traversal(node.borrow().left.clone(), depth + 1, max_depth, res);
}
if node.borrow().right.is_some() {
Self::traversal(node.borrow().right.clone(), depth + 1, max_depth, res);
}
}
}
//递归
int maxDepth = -1;
int res = 0;
public int FindBottomLeftValue(TreeNode root)
{
Traversal(root, 0);
return res;
}
public void Traversal(TreeNode root, int depth)
{
if (root.left == null && root.right == null)
{
if (depth > maxDepth)
{
maxDepth = depth;
res = root.val;
}
return;
}
if (root.left != null)
{
Traversal(root.left, depth + 1);
}
if (root.right != null)
{
Traversal(root.right, depth + 1);
}
return;
}
/*
* @lc app=leetcode id=513 lang=csharp
* 迭代法
* [513] Find Bottom Left Tree Value
*/
// @lc code=start
public class Solution
{
public int FindBottomLeftValue(TreeNode root)
{
Queue<TreeNode> que = new Queue<TreeNode>();
if (root != null)
{
que.Enqueue(root);
}
int ans = 0;
while (que.Count != 0)
{
int size = que.Count;
for (var i = 0; i < size; i++)
{
var curNode = que.Peek();
que.Dequeue();
if(i == 0){
ans = curNode.val;
}
if (curNode.left != null)
{
que.Enqueue(curNode.left);
}
if (curNode.right != null)
{
que.Enqueue(curNode.right);
}
}
}
return ans;
}
}
// @lc code=end