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