题目如下：　

Invert a binary tree.Example:Input:     4   /   \  2     7 / \   / \1   3 6   9Output:     4   /   \  7     2 / \   / \9   6 3   1

分析：

　　?问题，翻转二叉树。怎么翻转看图就知道了。

　　观察一下不难发现：翻转二叉树的定义就是根-左-右变成了根-“左”（右）-“右”（左）

　　那么：实现翻转的方法，往下遍历递归即可。

　　方法如下：

　　1.若当前节点为空，返回空。递归出口。

　　2.定义一个右节点：由翻转当前节点的右子树所得。

　　3.定义一个左节点：由翻转当前节点的左子树所得。

　　4.当前节点->“左”节点=“右”节点

　　5.当前节点->“右”节点=“左”节点

　　

　　方法本质上就两条：

　　　　I.反转二叉树的左右子树

　　　　II.将左右子树交换

　　其中I又是一个反转二叉树的问题，所以递归解决。

 

代码如下：

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     struct TreeNode *left; *     struct TreeNode *right; * }; */struct TreeNode* invertTree(struct TreeNode* root) {        if(root==NULL)        return NULL;    struct TreeNode *R = invertTree(root->right);//重构的右节点    struct TreeNode *L = invertTree(root->left); //重构的左节点    root->right=L;//“右”节点    root->left=R;//“左”节点    return root; }

 

注：关于这题还有个小故事，我觉得光Homebrew就可以秒掉整本数据结构……

Trivia:This problem was inspired by this original tweet by Max Howell: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.

我有点理解为什么我看不懂开源代码了。