你會翻轉(zhuǎn)二叉樹嗎？不會，那對不起滾吧！

事件的起因是 Max Howell 在谷歌面試碰壁之后發(fā)推特吐槽 ，大致講的是：谷歌90%的工程師都使用你寫的(Homebrew)，但是你不能在白板上寫出翻轉(zhuǎn)二叉樹，所以你滾吧??

連大神在面試的時候都折了戟，為了防止悲劇的再次發(fā)生，同志們、同學們我們還是先學學怎么翻轉(zhuǎn)二叉樹吧！

下面是從 LeetCode 中摘來的原題目：

其實就題目本身來講并不算是晦澀難懂的高難度問題，但是這是在我們后來看這道題，如果一開始是你從未見過，我估計很多人也有可能會蒙住吧！下面分別用Objective-C和Python3來解這道題。兩種代碼中分別給出了遞歸方式和非遞歸方式，默認實現(xiàn)了二叉樹。

解題思路

Objective-C和Python3的解題思路是完全一致的，基本上就是從把Python3翻譯成Objective-C代碼。

首先我們看題目中的要求，根節(jié)點是 4 ，4 的左子樹是 2 ，右子樹是 7 ，翻轉(zhuǎn)之后根節(jié)點仍然是 4 ，左子樹和右子樹交換。與此同時，以左子樹和右子樹為根節(jié)點的二叉樹都會跟過來，1、3仍然是 2 的子樹，6、9也還是 7 的子樹。接下來再次分別翻轉(zhuǎn)。

Objective-C代碼實現(xiàn)

// 遞歸翻轉(zhuǎn)
- (void)invertBinaryTreeByRecursion:(Node *)rootNode {
    if (rootNode == nil) return;
    Node *temp = rootNode.leftChild;
    rootNode.leftChild = rootNode.rightChild;
    rootNode.rightChild = temp;
    
    [self invertBinaryTreeByRecursion:rootNode.leftChild];
    [self invertBinaryTreeByRecursion:rootNode.rightChild];
}

// 非遞歸翻轉(zhuǎn)
- (void)invertBinaryTree:(Node *)rootNode {
    
    if (rootNode == nil) return;
    
    NSMutableArray *queue = [NSMutableArray arrayWithObject:rootNode];
    
    while (queue.count) {
        
        Node *curNode = queue.firstObject;
        [queue removeObjectAtIndex:0];
        
        Node *temp = curNode.leftChild;
        curNode.leftChild = curNode.rightChild;
        curNode.rightChild = temp;
        
        if (curNode.leftChild) {
            [queue addObject:curNode.leftChild];
        }
        
        if (curNode.rightChild) {
            [queue addObject:curNode.rightChild];
        }
    }
    
}

Python3代碼實現(xiàn)

# 遞歸
def invertBinaryTreeByRecursion(self, root):
    if root is None:
        return

    root.lchild, root.rchild = root.rchild, root.lchild

    self.invertBinaryTreeByRecursion(root.lchild)
    self.invertBinaryTreeByRecursion(root.rchild)

# 非遞歸
def invertBinaryTree(self, root):
    if root is None:
        return

    queue = [root]

    while queue:
        curNode = queue.pop(0)

        curNode.lchild, curNode.rchild = curNode.rchild, curNode.lchild

        if curNode.lchild is not None:
            queue.append(curNode.lchild)

        if curNode.rchild is not None:
            queue.append(curNode.rchild)