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 的文章
