圖論應用: 找出二元樹最後一層最左邊的值 Bottom Left Tree Value_Leetcode #513

閱讀時間約 6 分鐘

題目敘述

題目會給定一棵二元樹的根結點,要求我們找出這棵二元樹最後一層最左邊的值


題目的原文敘述


測試範例

Example 1:

raw-image
Input: root = [2,1,3]
Output: 1

Example 2:

raw-image
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, 10^4].

節點總數量界於1~一萬之間。

  • -2^31 <= Node.val <= 2^31- 1

所有節點值都落在32bits整數範圍內。


演算法 BFS 或 DFS

其實和前面介紹過的那題 二元樹的右側視角 很像。

這題題目所求為 二元樹最後一層最左邊的值

那就依照題意,廣度優先BFS或深度優先DFS拜訪到最後一層,紀錄左手邊第一個遇到的節點值即可


程式碼 BFS

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

from collections import deque

class Solution:
def findBottomLeftValue(self, root: TreeNode) -> int:

traversal_queue = [ root ]

bottom_left = root

while traversal_queue:

next_level = []

for idx, node in enumerate(traversal_queue):

if not idx:
# update bottom left as the first node on current level
bottom_left = node

# add child node to next level traversal queue if they exist

if node.left:
next_level.append( node.left )

if node.right:
next_level.append( node.right )

traversal_queue = next_level

return bottom_left.val

複雜度分析

時間複雜度:

BFS廣度優先拜訪整棵樹,每個節點至多拜訪一次。所需時間為O(n)

空間複雜度:

BFS quque所需成本為O(n),最大成本落在最後一層。


程式碼 DFS

class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:

def finder(node, level):

if not node:
return

if level > finder.level:
finder.bottom_left = node.val
finder.level = level

finder(node.left, level+1)
finder(node.right, level+1)
return
# -------------------------------

finder.bottom_left = None
finder.level = 0

finder(node=root, level=1)

return finder.bottom_left

時間複雜度:

DFS廣度優先拜訪整棵樹,每個節點至多拜訪一次。所需時間為O(n)

空間複雜度:

DFS recursion stack所需成本為O(n),最大深度為整棵樹的最大樹高。


關鍵知識點

條條大路通羅馬,只要掌握基本原理,遇到新的題目也能根據基本的圖論演算法DFS、BFS配合題意的需求去構建出解題的演算法


另外,還有一個衍伸題,假如題目問我們最後一層最右邊的值? 要怎麼改?

也很容易,把拜訪順序改成從右到左,取最後一層第一個遇到的節點值,就可以囉!


Reference:

[1] Find Bottom Left Tree Value - LeetCode

84會員
423內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
題目敘述 題目會給定一個二維陣列grid,代表每顆橘子分布的位置和初始狀態。 0: 這個格子點沒有東西。 1: 這個格子點有一顆新鮮的橘子。 2: 這個格子點有一顆壞掉的橘子。 壞掉的橘子上面的黴菌, 每隔一個週期,可以向上、下、左、右 N4四連通的格子點感染一次。 請問,最少需要多
題目敘述 題目會給定一個參數n代表人口總數,和對應的信任關係陣列trust,陣列元素都是pair都以,[a, b]的形式呈現,代表a信任b。 要求我們找出法官是誰,返回法官的ID? 成為法官的條件: 1.每個人(除了法官自己之外)都信任法官。 2.法官不信任別人。 題目的原文敘述
題目敘述 題目會給我們一個參數k 和 目標值n。 請問我們從1~9內挑k個相異的數字,使得他們的總和為n 的組合數有多少? 挑選時,每個數字必須相異,而且每個數字只能選一次。 題目的原文敘述 測試範例 Example 1: Input: k = 3, n = 7 Output: [
題目敘述 題目會給我們一個傳統手機的數字鍵盤 和一個數字鍵的輸入字串digits,要求我們列舉出所有輸入字串digits可能對應到的英文字母的排列。 例如輸入digits="23" 那對應到的英文字母排列就是"ad", "ae", "af", "bd", "be", "bf", "cd", "
題目敘述 題目會給我們一個4位數字的數字鎖,還有解鎖的密碼target,和陷阱數字deadends(假如遇到的會鎖會直接卡住,不能在撥動轉盤了)。 預設開始的狀態是0000,請問,最少要撥動轉盤幾次才能解鎖? 題目的原文敘述 測試範例 Example 1: Input: deaden
題目敘述 題目給定一個二維陣列maze代表迷宮的布局, 其中標記為"."的地方代表可通過,標記為"+"代表牆壁不可通過。 每次移動的時候,可以選擇往上、下、左、右移動一格。 請問從出發點entrace開始走的話,抵達迷宮出口最短距離的步數是多少? 如果無解的話,返回-1。 題目的原文敘述
題目敘述 題目會給定一個二維陣列grid,代表每顆橘子分布的位置和初始狀態。 0: 這個格子點沒有東西。 1: 這個格子點有一顆新鮮的橘子。 2: 這個格子點有一顆壞掉的橘子。 壞掉的橘子上面的黴菌, 每隔一個週期,可以向上、下、左、右 N4四連通的格子點感染一次。 請問,最少需要多
題目敘述 題目會給定一個參數n代表人口總數,和對應的信任關係陣列trust,陣列元素都是pair都以,[a, b]的形式呈現,代表a信任b。 要求我們找出法官是誰,返回法官的ID? 成為法官的條件: 1.每個人(除了法官自己之外)都信任法官。 2.法官不信任別人。 題目的原文敘述
題目敘述 題目會給我們一個參數k 和 目標值n。 請問我們從1~9內挑k個相異的數字,使得他們的總和為n 的組合數有多少? 挑選時,每個數字必須相異,而且每個數字只能選一次。 題目的原文敘述 測試範例 Example 1: Input: k = 3, n = 7 Output: [
題目敘述 題目會給我們一個傳統手機的數字鍵盤 和一個數字鍵的輸入字串digits,要求我們列舉出所有輸入字串digits可能對應到的英文字母的排列。 例如輸入digits="23" 那對應到的英文字母排列就是"ad", "ae", "af", "bd", "be", "bf", "cd", "
題目敘述 題目會給我們一個4位數字的數字鎖,還有解鎖的密碼target,和陷阱數字deadends(假如遇到的會鎖會直接卡住,不能在撥動轉盤了)。 預設開始的狀態是0000,請問,最少要撥動轉盤幾次才能解鎖? 題目的原文敘述 測試範例 Example 1: Input: deaden
題目敘述 題目給定一個二維陣列maze代表迷宮的布局, 其中標記為"."的地方代表可通過,標記為"+"代表牆壁不可通過。 每次移動的時候,可以選擇往上、下、左、右移動一格。 請問從出發點entrace開始走的話,抵達迷宮出口最短距離的步數是多少? 如果無解的話,返回-1。 題目的原文敘述
你可能也想看
Google News 追蹤
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
上篇進一步認識基本的圖形架構與三大 Graph 算法,那首先從 shortest path 開始,我們會陸續去理解這些算法,以及可能的應用,如果還沒有看過上一篇的,可以點以下連結~那我們就開始吧! 【圖論Graph】Part1:初探圖形與圖形演算法之應用
Thumbnail
本篇文章深入介紹了圖形的基本概念、組成和應用。從圖形的基本組成,到圖的類型與種類,再到圖形演算法的三大類型,本文將接續圖形領域的深入學習,並分享了對圖形的初步認識和學習方向的小心得。希望對正在學習圖形的人有所幫助。
Thumbnail
圖形演算法在資料處理上扮演重要角色。本文介紹圖形的歷史、定義、技術用途,以及為什麼我們要關心圖形演算法。文末還提及圖形演算法在機器學習領域的應用。下次將介紹更詳細的圖形演算法內容。
Thumbnail
  回想起剛從機械系畢業時,我懂得怎麼計算,也熟悉各種機械理論。但真正要自己設計時,卻只能朦朧應用,可以說是亂兜各種機件,最後拼出了一個四不像的奇怪機構。   而十年後的現在,對機構學的熱情讓我始終從事「能應用『動力機構』」的工作。看過許多機械構造也自己鑽研許多,才能達到現在類「得心應手」的地步。
Thumbnail
因最近看到又有人討論起推背圖後,我不禁回想去過去台灣這邊也是拿推背圖來說誰當選。 所以整理一下過去對於推背圖的一些瞭解,重新解剖一下解讀的走向。 首先要先弄清楚推背圖的規律,我整頓完思緒後基本上可以歸納幾點。 1.此預言是描述[中國大陸的最大勢力],所以如今的現在,描述的只會是[中共國],而非[中華
Thumbnail
-> 這篇在說什麼 這篇文章提供一個科目圖的視角來分析科系,每個學生可以依照自己喜歡的工作,來反推出需要學習的科目,進而反推出選這科系的成本效益值 此篇也會leverage這科目圖工具去解除一些大家的誤解/盲點 出路廣的科系就是好科系? 是否有盲點? 出路廣的科系還有分類? 前言 如何判斷?
哈耶克這種人之所以能在漢語圈傳播得很遠,有一點就是因為他的行為模式很像是胡適那種士大夫,這種人就非常精確地體現了胡適所謂的那種「對政治不感興趣的興趣」。所謂「不感興趣的興趣」,從最難聽的方向進行惡意解釋,恰好就是鮑德溫用來罵羅瑟米爾爵士的那句話:他們追求不負責任的權力,正如歷代的婊子追求牌坊。
Thumbnail
 最近接觸一位熱愛八九十年代流行歌曲的小學生,他在言談間也不時哼起一兩句,使我不期然想起小時候的自己。  香江小故事 「I, I, I was born in Beijing,不知命運是誰定。」黎天
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
上篇進一步認識基本的圖形架構與三大 Graph 算法,那首先從 shortest path 開始,我們會陸續去理解這些算法,以及可能的應用,如果還沒有看過上一篇的,可以點以下連結~那我們就開始吧! 【圖論Graph】Part1:初探圖形與圖形演算法之應用
Thumbnail
本篇文章深入介紹了圖形的基本概念、組成和應用。從圖形的基本組成,到圖的類型與種類,再到圖形演算法的三大類型,本文將接續圖形領域的深入學習,並分享了對圖形的初步認識和學習方向的小心得。希望對正在學習圖形的人有所幫助。
Thumbnail
圖形演算法在資料處理上扮演重要角色。本文介紹圖形的歷史、定義、技術用途,以及為什麼我們要關心圖形演算法。文末還提及圖形演算法在機器學習領域的應用。下次將介紹更詳細的圖形演算法內容。
Thumbnail
  回想起剛從機械系畢業時,我懂得怎麼計算,也熟悉各種機械理論。但真正要自己設計時,卻只能朦朧應用,可以說是亂兜各種機件,最後拼出了一個四不像的奇怪機構。   而十年後的現在,對機構學的熱情讓我始終從事「能應用『動力機構』」的工作。看過許多機械構造也自己鑽研許多,才能達到現在類「得心應手」的地步。
Thumbnail
因最近看到又有人討論起推背圖後,我不禁回想去過去台灣這邊也是拿推背圖來說誰當選。 所以整理一下過去對於推背圖的一些瞭解,重新解剖一下解讀的走向。 首先要先弄清楚推背圖的規律,我整頓完思緒後基本上可以歸納幾點。 1.此預言是描述[中國大陸的最大勢力],所以如今的現在,描述的只會是[中共國],而非[中華
Thumbnail
-> 這篇在說什麼 這篇文章提供一個科目圖的視角來分析科系,每個學生可以依照自己喜歡的工作,來反推出需要學習的科目,進而反推出選這科系的成本效益值 此篇也會leverage這科目圖工具去解除一些大家的誤解/盲點 出路廣的科系就是好科系? 是否有盲點? 出路廣的科系還有分類? 前言 如何判斷?
哈耶克這種人之所以能在漢語圈傳播得很遠,有一點就是因為他的行為模式很像是胡適那種士大夫,這種人就非常精確地體現了胡適所謂的那種「對政治不感興趣的興趣」。所謂「不感興趣的興趣」,從最難聽的方向進行惡意解釋,恰好就是鮑德溫用來罵羅瑟米爾爵士的那句話:他們追求不負責任的權力,正如歷代的婊子追求牌坊。
Thumbnail
 最近接觸一位熱愛八九十年代流行歌曲的小學生,他在言談間也不時哼起一兩句,使我不期然想起小時候的自己。  香江小故事 「I, I, I was born in Beijing,不知命運是誰定。」黎天