513. 找树左下角的值

Difficulty
Medium
Tags
二叉树
URL
https://leetcode-cn.com/problems/find-bottom-left-tree-value/
Star
给定一个二叉树，在树的最后一行找到最左边的值。
示例 1:
输入:

    2
   / \
  1   3

输出:
1
示例 2:
输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:
7
注意: 您可以假设树（即给定的根节点）不为 NULL。

法1 层次遍历 bfs

思路
采用层次遍历，每次将每一层的第一个节点更新为result。遍历结束，直接返回result即可
题解
# 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:
        if root is None:
            return 0
        queue = []
        queue.append(root)
        result = None
        while len(queue) > 0:
            lenTemp = len(queue)
            # 每次都更新result
            result = queue[0].val
            while lenTemp > 0:
                node = queue.pop(0)
                lenTemp -= 1
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result

法2 先序遍历 DFS

思路
设置全局变量，最大深度maxDepth及最终结果result。从上往下遍历，遍历的时候把当前层的高度也作为参数传进递归函数。在函数内部判断当前高度是否大于最大高度，如果是，那么更新maxDepth和result，这样同一层右边的节点就不会再更新了。
题解
# 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:
        self.result = 0
        self.maxDepth = -1
        self.dfs(node=root, depth=0)
        return self.result
    
    def dfs(self, node, depth):
        if node.left is None and node.right is None:
            if depth > self.maxDepth:
                self.maxDepth = depth
                self.result = node.val
        if node.left:
            self.dfs(node.left, depth+1)
        if node.right :
            self.dfs(node.right, depth+1)
        return