---
title: 【LeetCode】0226. Invert Binary Tree
date: 2018-12-16
is_modified: false
disqus: cynthiahackmd
categories:
- "面試刷題"
tags:
- "LeetCode"
---

{%hackmd @CynthiaChuang/Github-Page-Theme %}

Invert a binary tree.
<!--more-->
<br>

**Example:**

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9


Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

<br>

**Trivia:**
This problem was inspired by [this original tweet](https://twitter.com/mxcl/status/608682016205344768) by [Max Howell](https://twitter.com/mxcl):

> Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

<br>

**Related Topics:** `Tree`

## 解題邏輯與實作
頗為知名的一題(笑)，但基本上沒什麼難度，只需要互換節點左右兩邊的子樹即可。

### 遞迴
實作上就是採用**後序**（post-order）的方式尋訪整棵樹，並在尋訪父節點時交換左右子樹。

class Solution:
    def invertTree(self, root):
        self.invert(root)
        return root
        
    def invert(self, root):
        if root is None:
            return
        
        self.invertTree(root.left)
        self.invertTree(root.right)
            
        root.left, root.right =  root.right, root.left            

### 最速解
我寫這篇就是為了分享這個，在 [Ruby China](https://ruby-china.org/topics/25977) 上看到**如何用最少字元翻轉二元樹**XDDDDD

class Solution:
  def invertTree(self, root):
    print("(╯°□°)╯︵ ǝǝɹʇ ʎɹɐuıq")
    return root

## 其他連結
1. [【LeetCode】0000. 解題目錄](/x62skqpKStKMxRepJ6iqQQ)

## 參考資料
1. [Invert Binary Tree｜LeetCode](https://leetcode.com/problems/invert-binary-tree/)
2. [Homebrew 作者被 Google 鄙视了… ｜Ruby China](https://ruby-china.org/topics/25977)

<br><br>

> **本文作者**： 辛西亞．Cynthia
> **本文連結**： [辛西亞的技能樹](https://cynthiachuang.github.io/LeetCode-0226-Invert-Binary-Tree) / [hackmd 版本](https://hackmd.io/@CynthiaChuang/LeetCode-0226-Invert-Binary-Tree)
> **版權聲明**： 部落格中所有文章，均採用 [姓名標示-非商業性-相同方式分享 4.0 國際](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en) (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！