给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
提示:
二叉树的节点个数的范围是 [1,104]
-231 <= Node.val <= 231 - 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value
python
# 513.找树左下角的值
class Solution:
def findBottomLeftValue(self, root: TreeNode) -> int:
"""
前序递归
:param root:
:return:
"""
max_depth = -float("INF")
leftMostVal = 0
def traverse(root, curDepth):
nonlocal max_depth, leftMostVal
# 终止条件
if not root.left and not root.right:
if curDepth > max_depth:
max_depth = curDepth
leftMostVal = root.val
if root.left:
curDepth += 1
traverse(root.left, curDepth)
curDepth -= 1
if root.right:
curDepth += 1
traverse(root.right, curDepth)
curDepth -= 1
traverse(root, 0)
return leftMostVal
class Solution2:
def findBottomLeftValue(self, root: TreeNode) -> int:
"""
迭代层序遍历
:param root:
:return:
"""
from collections import deque
queue = deque()
if root:
queue.append(root)
res = 0
while queue:
queueLen = len(queue)
for i in range(queueLen):
if i == 0:
res = queue[i].val
cur = queue.popleft()
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
return res
golang
package binaryTree
import "container/list"
var maxDepth int
var value int
func findBottomLeftValue(root *TreeNode) int {
if root.Left == nil && root.Right == nil {
return root.Val
}
findLeftValue(root, maxDepth)
return value
}
func findLeftValue(root *TreeNode, deep int) {
// 最左边的值在左边
if root.Left == nil && root.Right == nil {
if deep > maxDepth {
value = root.Val
maxDepth = deep
}
}
// 递归左树
if root.Left != nil {
deep++
findLeftValue(root.Left, deep)
deep--
}
// 递归右树
if root.Right != nil {
deep++
findLeftValue(root.Right, deep)
deep--
}
}
// 迭代法
func findBottomLeftValue2(root *TreeNode) int {
queue := list.New()
var res 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 {
res = node.Val
}
if node.Left != nil {
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
}
}
return res
}