經典圖論面試題 Invert Binary Tree_Leetcode #226

更新於 發佈於 閱讀時間約 2 分鐘
raw-image

這題的題目在這裡: 226. Invert Binary Tree

題目敘述

題目會給我們一顆二元樹的根節點,要求我們對齊根節點正中央的虛擬分割線,反轉整顆二元樹


測試範例

Example 1:

raw-image
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

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

Example 3:

Input: root = []
Output: []

約束條件

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

演算法


利用DFS遞迴探索整顆樹的性質,來進行鏡像反轉

  1. 交換左子樹和右子樹(在程式碼中,就是交換root.left 和 root.right)
  2. 遞迴處理下一層(這邊我們使用DFS 比較簡潔)
  3. 返回樹根root,樹根本身保持不動


raw-image

程式碼

class Solution:
 def invertTree(self, root: TreeNode) -> TreeNode:
  
  if root:
   # General case:
   
   # invert child node of current root
   root.left, root.right = root.right, root.left
   
   # invert subtree with DFS
   self.invertTree( root.left )
   self.invertTree( root.right )
   
   return root
  
  else:
   # Base case:
   # empty tree
   
   return None

複雜度分析

時間複雜度:O( n )

O( n ) 每個節點最多拜訪一次。

空間複雜度:O( n )

O( n ) 空間成本耗費在遞迴呼叫時所建立的call stack,

最深的那一層在最後一層,當樹向左歪斜或向右歪斜時,
最深的深度可以到O( n )


Reference

[1] Python/JS/Java/Go/C++ O(n) by DFS [w/ Visualization] — Invert Binary Tree — LeetCode

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
96會員
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/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
2024/09/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
看更多
你可能也想看
Thumbnail
家中修繕或裝潢想要找各種小零件時,直接上網採買可以省去不少煩惱~看看Sylvia這回為了工地買了些什麼吧~
Thumbnail
家中修繕或裝潢想要找各種小零件時,直接上網採買可以省去不少煩惱~看看Sylvia這回為了工地買了些什麼吧~
Thumbnail
👜簡單生活,從整理包包開始!我的三款愛用包+隨身小物清單開箱,一起來看看我每天都帶些什麼吧🌿✨
Thumbnail
👜簡單生活,從整理包包開始!我的三款愛用包+隨身小物清單開箱,一起來看看我每天都帶些什麼吧🌿✨
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
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
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,
Thumbnail
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,
Thumbnail
題目會給我們一顆二元樹的根結點,要求我們找出每一層最大的節點值。
Thumbnail
題目會給我們一顆二元樹的根結點,要求我們找出每一層最大的節點值。
Thumbnail
題目會給我們節點總數目n、左子樹的關係陣列、右子樹的關係陣列,要求我們驗證在給定的條件下,能不能構成一顆合法的二元樹。
Thumbnail
題目會給我們節點總數目n、左子樹的關係陣列、右子樹的關係陣列,要求我們驗證在給定的條件下,能不能構成一顆合法的二元樹。
Thumbnail
題目會給定給我們一顆二元樹的根結點, 要求我們輸出上下顛倒的Level-order traversal的拜訪結果。
Thumbnail
題目會給定給我們一顆二元樹的根結點, 要求我們輸出上下顛倒的Level-order traversal的拜訪結果。
Thumbnail
題目會給我們一顆二元樹的根節點, 要求我們對齊根節點正中央的虛擬分割線,反轉整顆二元樹。
Thumbnail
題目會給我們一顆二元樹的根節點, 要求我們對齊根節點正中央的虛擬分割線,反轉整顆二元樹。
Thumbnail
題目會給定一顆二元樹的根結點,要求我們驗證這一顆樹是否為合法的二元搜索樹, 也就是所謂的Binary search tree, aka BST?
Thumbnail
題目會給定一顆二元樹的根結點,要求我們驗證這一顆樹是否為合法的二元搜索樹, 也就是所謂的Binary search tree, aka BST?
Thumbnail
Leetcode #101 Symmetric Tree 題目會給定一顆樹,要求我們判定這棵樹是不是左右鏡像對稱(Symmetric)。
Thumbnail
Leetcode #101 Symmetric Tree 題目會給定一顆樹,要求我們判定這棵樹是不是左右鏡像對稱(Symmetric)。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News