Homebrew是OS X平臺(tái)上的包管理工具虏两，在用Mac的程序員基本都知道這個(gè)工具漩绵。
HomeBrew的開發(fā)者是Max Howell左胞。然而面試谷歌時(shí)卻蛋疼了。Max Howell在Twitter發(fā)帖：
twitter
可見橱赠，會(huì)手寫反轉(zhuǎn)二叉樹多么重要。正好Leetcode上有這個(gè)題目箫津，下面進(jìn)入正題狭姨。
二叉樹是數(shù)據(jù)結(jié)構(gòu)里一個(gè)重要的概念。
而反轉(zhuǎn)二叉樹的基本意思就是下圖這樣苏遥。
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to:
4
/ \
7 2
/ \ / \
9 6 3 1
每一個(gè)節(jié)點(diǎn)的左右子樹對(duì)換饼拍，左右子樹的左右節(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
