【廣度優(yōu)先搜索】513.找樹左下角的值
給定一個二叉樹，在樹的最后一行找到最左邊的值。
示例 1:
輸入:
? ? 2
? ?/ \
? 1? ?3
輸出:
1
?
示例 2:
輸入:
? ? ? ? 1
? ? ? ?/ \
? ? ? 2? ?3
? ? ?/? ?/ \
? ? 4? ?5? ?6
? ? ? ?/
? ? ? 7
輸出:
7
題目解析
找到?樹 左下角的值，需要做的操作：
首先需要找到?每一層最左邊的值；
從 這些值中找到 最 下層的值
題目解答
方法：層次遍歷的 非遞歸方法
思路：
? 利用 層層次遍歷的?非遞歸方法 遍歷 每一層
保存每一層 的 最左邊一個元素；
最后取最后一個即為 答案
代碼展示
# 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 = rightclass Solution:def findBottomLeftValue(self, root: TreeNode) -> int:'''方法：隊列迭代 (層次遍歷非遞歸)'''# step 1:判空res = -1if not root:return res# step 2: 初始化隊列queue = collections.deque()queue.append(root)# step 3：層次遍歷 非遞歸法while queue:# step 4:每一層做遍歷for i in range(len(queue)):node = queue.popleft()# step 5:每一層 第一個元素if i==0:res = node.val# step 6：root 的 左子樹 入隊if node.left:queue.append(node.left)# step 7：root 的 右子樹 入隊if node.right:queue.append(node.right)return res
復(fù)雜度計算
?時間復(fù)雜度：O(N)，其中 N 是二叉樹的節(jié)點數(shù)。二叉樹的所有節(jié)點有且只會被訪問一次，因此時間復(fù)雜度為 O(N)。
-空間復(fù)雜度：O(N)，當樹為平衡二叉樹時，最多有N/2個樹節(jié)點入隊，使用 O(N)?大小的額外空間
運行結(jié)果
評論
圖片
表情