DFS應用: 在二元樹插入新的一層 Add one row to Tree_Leetcode #623

更新於 發佈於 閱讀時間約 4 分鐘

題目敘述

題目會給定一顆二元樹的根結點,
要求我們在指定的層樹d,插入新的一層,節點值為v。

原本的左、右子樹,就成為新的那一層的左子樹、右子樹。

題目的原文敘述


測試範例

Example 1:

raw-image
Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

Example 2:

raw-image
Input: root = [4,2,null,3,1], val = 1, depth = 3
Output: [4,2,null,1,1,3,null,null,1]

約束條件

Constraints:

  • The number of nodes in the tree is in the range [1, 10^4].

節點總數目介於1 ~ 一萬之間。

  • The depth of the tree is in the range [1, 10^4].

深度介於1 ~ 一萬之間。

  • -100 <= Node.val <= 100

節點值介於-100 ~ 100 之間。

  • -10^5 <= val <= 10^5

新插入的節點值介於 負十萬~正十萬之間。

  • 1 <= depth <= the depth of tree + 1

新插入的那一層介於1 ~ 原本的層樹+1


演算法 DFS + 共通模式


題目已經開門見山,要求在指定的層樹d,插入新的一層,節點值為v。


示意圖

raw-image


共通模式:

有一個很直覺的想法,先找到第d層,接著插入指定的新節點v,串接下一層d+1。

接著下方的節點都往後退一層即可。


也就是說,相當於

當d=n時,相當於往下走一層,接著在d-1層插入新節點v。


初始條件:

當d=1時,新插入的位置會取代原本的樹根,原本舊的樹根當作我的左子樹去串接。

當d=2時,剛好是樹根的下方左、右子樹分別插入新節點。原本舊的節點通通往後退一層。


程式碼 DFS + 共通模式


class Solution:
def addOneRow(self, root: TreeNode, v: int, d: int) -> TreeNode:

if not root:

# base case: empty tree
return None

elif d == 1:

# base case: add one row above original root
return TreeNode(v, left=root, right=None)

elif d == 2:

# base case: add one row just below original root
root.left = TreeNode(v, left=root.left, right=None)
root.right = TreeNode(v, left=None, right=root.right)

return root

else:

# general case: depth >= 3
# do it in DFS with common pattern
root.left = self.addOneRow(root.left, v, d-1)
root.right = self.addOneRow(root.right, v, d-1)

return root

複雜度分析 DFS + 共通模式

時間複雜度:

從上到下掃描到第d層,最深頂多到第n層,每個節點最多拜訪一次,所需時間為O(n)


空間複雜度:

從上到下掃描到第d層,最深頂多到第n層,每個節點最多拜訪一次,所需空間為O(n)


關鍵知識點 找出共通模式

根據題意,找出插入節點的共通模式。

發現可以用遞回結構描述:

在第d層插入新節點v,等價於 先往下走一層,接著在第(d-1)層插入新節點v


Reference:

[1] Add One Row to Tree - LeetCode

留言
avatar-img
留言分享你的想法!
媗日-avatar-img
2024/04/16
最近剛看完Python dfs,正好看到這篇👍雖然說我還不太熟?特別是那種從外部輸入進去的樹狀結構🤔
小松鼠-avatar-img
發文者
2024/04/17
媗日 這篇也是,用更宏觀的視角解說二魚數的拜訪,其實背後的DFS框架是相同的。只是位置換一下,就對應到三種不同的拜訪順序 inorder, preorder, postorderhttps://vocus.cc/article/6508091afd897800019e7a7c
小松鼠-avatar-img
發文者
2024/04/17
DFS 通常會用道遞回結構,遞回結構 白話的說就是觀察共通模式。找出 "當下這個局面的計算、操作共同規律是什麼"。可以藉由畫圖配合幾個小範例找出來。這邊有一個DFS統整、綜合應用的文章介紹。https://vocus.cc/article/660d6e95fd89780001df5de2
小松鼠-avatar-img
發文者
2024/09/11
從Python來學圖論Graph與DFS深度優先探索提及了這篇文章,趕快過去看看吧!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/02
 Binary Tree Inorder Traversal 題目給定一個二元樹的根結點。 請輸出中序拜訪(In-order traversal)的拜訪序列。 中序拜訪的定義: 1.拜訪左子樹。 2.拜訪目前的節點。 3.拜訪右子樹。
Thumbnail
2024/09/02
 Binary Tree Inorder Traversal 題目給定一個二元樹的根結點。 請輸出中序拜訪(In-order traversal)的拜訪序列。 中序拜訪的定義: 1.拜訪左子樹。 2.拜訪目前的節點。 3.拜訪右子樹。
Thumbnail
看更多
你可能也想看
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
題目敘述 題目會給定一顆二元樹的根結點, 要求我們在指定的層樹d,插入新的一層,節點值為v。 原本的左、右子樹,就成為新的那一層的左子樹、右子樹。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,6,3,1,5], val = 1, depth =
Thumbnail
題目敘述 題目會給定一顆二元樹的根結點, 要求我們在指定的層樹d,插入新的一層,節點值為v。 原本的左、右子樹,就成為新的那一層的左子樹、右子樹。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,6,3,1,5], val = 1, depth =
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點, 要求我們計算滿足局部路徑節點和=targetSum的數目有多少? 註: 局部路徑節點和 =由節點a往下走到某個節點b,這個區間內的節點值總和 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,-3,3
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點, 要求我們計算滿足局部路徑節點和=targetSum的數目有多少? 註: 局部路徑節點和 =由節點a往下走到某個節點b,這個區間內的節點值總和 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,-3,3
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們判定這是否為一顆合法的奇偶二元樹? 奇偶二元樹的定義: 從上到下依序是第0層、第一層、...、第n層 偶數層裡面的節點值都必須是奇數,而且由左到右嚴格遞增。 奇數層裡面的節點值都必須是偶數,而且由左到右嚴格遞減。 題目的原文敘述 測試
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們判定這是否為一顆合法的奇偶二元樹? 奇偶二元樹的定義: 從上到下依序是第0層、第一層、...、第n層 偶數層裡面的節點值都必須是奇數,而且由左到右嚴格遞增。 奇數層裡面的節點值都必須是偶數,而且由左到右嚴格遞減。 題目的原文敘述 測試
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們找出這棵二元樹最後一層最左邊的值。 題目的原文敘述 測試範例 Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6
Thumbnail
題目敘述 題目會給定一棵二元樹的根結點,要求我們找出這棵二元樹最後一層最左邊的值。 題目的原文敘述 測試範例 Example 1: Input: root = [2,1,3] Output: 1 Example 2: Input: root = [1,2,3,4,null,5,6
Thumbnail
題目敘述 題目會給我們一棵BST二元搜索樹的根結點root,還有一個指定的目標值key。 要求我們在樹中刪除帶有這個key值的節點,並且返回更新過後二元搜索樹的樹根root。 題目的原文敘述 測試範例 Example 1: Input: root = [5,3,6,2,4,null,
Thumbnail
題目敘述 題目會給我們一棵BST二元搜索樹的根結點root,還有一個指定的目標值key。 要求我們在樹中刪除帶有這個key值的節點,並且返回更新過後二元搜索樹的樹根root。 題目的原文敘述 測試範例 Example 1: Input: root = [5,3,6,2,4,null,
Thumbnail
題目敘述 題目會給我們一棵二元搜索樹的根結點root,還有一個指定的目標值val。 要求我們找出在樹中對應到目標值val的節點,假如找不到,請回傳null( null在Python就是None)。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,
Thumbnail
題目敘述 題目會給我們一棵二元搜索樹的根結點root,還有一個指定的目標值val。 要求我們找出在樹中對應到目標值val的節點,假如找不到,請回傳null( null在Python就是None)。 題目的原文敘述 測試範例 Example 1: Input: root = [4,2,
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News