513. Find Bottom Left Tree Value

Loading...LeetCode

二叉树层序遍历，优先BFS做：

class Solution:
    def findBottomLeftValue(self, root):      
        res = root.val
        queue = collections.deque([root])
        while queue:
            n_ = len(queue)
            for i in range(n_):
                node = queue.popleft()
                if i == 0:
                    res = node.val
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
                
        return res

也可以拿DFS做，左侧优先，记录当前深度和最大深度，当前深度>最大深度的时候，记录所在node的值。

# 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 __init__(self):
        self.bottomLeft = 0
        self.maxRow = -1
        
    def dig(self, root, row):
        # 挖到底，停下
        if not root: 
            return
        # 没到底的话，先挖左边（优先最左边的值）
        self.dig(root.left, row + 1)
        # 如果挖的过程里最大深度被更新了，就同时用root更新 leftmost value
        if row > self.maxRow:
            self.maxRow = row
            self.bottomLeft = root.val
        # 左边挖到最底了，再回来挖右边
        self.dig(root.right, row + 1)
        
    def findBottomLeftValue(self, root):      
        self.dig(root, 0)
        return self.bottomLeft