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

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

題目敘述

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

測試範例

Example 1:

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

Example 2:

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，樹根本身保持不動。

程式碼

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