## Leetcode | 0513. Find the value in the lower left corner of the tree [Python]

Wonz 2021-01-20 23:13:36
leetcode value lower left corner

## Problem

LeetCode

Given the `root` of a binary tree, return the leftmost value in the last row of the tree.

Example 1:

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-s9lEcua7-1611152690383)(https://assets.leetcode.com/uploads/2020/12/14/tree1.jpg)]

``````Input: root = [2,1,3]
Output: 1
``````

Example 2:

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-50uusBeG-1611152690392)(https://assets.leetcode.com/uploads/2020/12/14/tree2.jpg)]

``````Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7
``````

Constraints:

• The number of nodes in the tree is in the range `[1, 104]`.
• `-231 <= Node.val <= 231 - 1`

## problem

Power button

Given a binary tree , Find the leftmost value in the last row of the tree .

Example 1:

`````` Input :
2
/ \
1 3
Output :
1
``````

Example 2:

`````` Input :
1
/ \
2 3
/ / \
4 5 6
/
7
Output :
7
``````

Be careful : You can assume that the tree （ The given root node ） Not for NULL.

## Ideas

BFS

`````` routine BFS It's up and down , First left then right level traversal . We can change BFS traversal order , First up and then down , First right then left , In this way, the last node traversed must be the node in the lower left corner , Finally, just return the node value directly .
``````

### Python3 Code

``````# 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:
import collections
q = collections.deque()
q.append(root)
while q:
node = q.popleft()
# First right then left
if node.right:
q.append(node.right)
if node.left:
q.append(node.left)
# The last one must be the node in the bottom left corner
return node.val
``````