黄哥Python,LeetCode Find Bottom Left Tree Value解题思路

LeetCode 513 题

513. Find Bottom Left Tree Value

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
Note: You may assume the tree (i.e., the given root node) is not NULL.

这个题目看起来很复杂，分析题目后，一定是用bfs 搜索去解决，二叉树的bfs遍历，惯性思维先添加左子树，这个题目先添加右子树，几行代码就搞定。 ​​​

第一， Python 代码， 用非递归遍历，题目已经假定了root 非空， 用队列（Python 用list 模拟队列），先添加root到队列中，出队列，再判右子树不为空，就添加右子树，再判断左子树是不是为空，非空添加左子树。

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution: 

 '''黄哥Python培训 黄哥所写'''
 def findBottomLeftValue(self, root: TreeNode) -> int:
 res = root.val
 q = [root]
 while q:
 node = q.pop(0)
 res = node.val
 if node.right:
 q.append(node.right) 
 if node.left:
 q.append(node.left) 
 return res

第二，Go 语言代码，用的递归，原因是Go 中slice 不好模拟队列，就用递归来写，先求树的高度，再写bfs，bfs一定要先调用右子树，再左子树，bfs 传三个参数，root, res 用指针返回值，还有一个是层level。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 * Val int
 * Left *TreeNode
 * Right *TreeNode
 * }
 */
// 黄哥Python培训 黄哥所写
func findBottomLeftValue(root *TreeNode) int {
 var res int
 bfs(root, &res, height(root))
 return res
}
func bfs(root *TreeNode, res *int, level int) {
 if root == nil {
 return
 }
 if level == 1 {
 *res = root.Val
 }else if level > 1 {
 bfs(root.Right, res, level - 1)
 bfs(root.Left, res, level - 1) 

 }
}
func height(root *TreeNode) int {
 if root == nil {
 return 0
 }
 return int(math.Max(float64(height(root.Left)), float64(height(root.Right)))) + 1
}

閱讀更多 黃哥Python 的文章

關鍵字: Python 添加 二叉树