Homebrew是OS X平臺(tái)上的包管理工具，在用Mac的程序員基本都知道這個(gè)工具。
HomeBrew的開(kāi)發(fā)者是Max Howell。然而面試谷歌時(shí)卻蛋疼了。Max Howell在Twitter發(fā)帖：

twitter

可見(jiàn)，會(huì)手寫(xiě)反轉(zhuǎn)二叉樹(shù)多么重要。正好Leetcode上有這個(gè)題目，下面進(jìn)入正題。

二叉樹(shù)是數(shù)據(jù)結(jié)構(gòu)里一個(gè)重要的概念。
而反轉(zhuǎn)二叉樹(shù)的基本意思就是下圖這樣。
Invert a binary tree.

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

to:

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

每一個(gè)節(jié)點(diǎn)的左右子樹(shù)對(duì)換，左右子樹(shù)的左右節(jié)點(diǎn)也需要交換，這種時(shí)候很容易想到的就是遞歸的方法。
下面是在Leetcode 通過(guò)的C++代碼：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        TreeNode* tmp;
        if(!root)
            return NULL;
        if(root->left)
            root->left=invertTree(root->left);
        if(root->right)
            root->right=invertTree(root->right);
        tmp=root->left;
        root->left=root->right;
        root->right=tmp;
        return root;     
    }
};

至于非遞歸的做法也很簡(jiǎn)單，借助一個(gè)隊(duì)列就可以實(shí)現(xiàn)，在C++里，直接使用標(biāo)準(zhǔn)庫(kù)的queue就可以。
首先取根節(jié)點(diǎn)入隊(duì)，再出隊(duì)，交換它的左右節(jié)點(diǎn)，再將左右節(jié)點(diǎn)入隊(duì)，這樣就可以以層次遍歷的方法，處理每一層的節(jié)點(diǎn)。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode *> node_queue;
        
        if(root == NULL)
            return root;
        node_queue.push(root);
        while(node_queue.size()>0) 
        {
            TreeNode* pFrontNode = node_queue.front();
            node_queue.pop();
            TreeNode *tmp = pFrontNode->left;
            pFrontNode->left = pFrontNode->right;
            pFrontNode->right = tmp;
            if(pFrontNode->left)
                node_queue.push(pFrontNode->left);
            if(pFrontNode->right)
                node_queue.push(pFrontNode->right);
        }
        return root;
        
    }
};

最近在看Python，用Python實(shí)現(xiàn)也一樣，遞歸解法：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root is None:
            return None
        root.left,root.right = self.invertTree(root.right),self.invertTree(root.left)
        return root
        

非遞歸

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        queue = collections.deque()
        if root:
            queue.append(root)
        while queue:
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            node.left,node.right = node.right,node.left
        return root