大牛没有能做出来的题，我们要好好做一做
Invert a binary tree.
4/ \ 27 / \ / \1 3 6 9
to
4/ \ 72 / \ / \9 6 3 1
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 fuck off.
递归解决方案：
/** * 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){if(root ==NULL) return root;TreeNode* node = invertTree(root->left);root->left = invertTree(root->right);root->right = node;return root;}};
非递归解决方案：
TreeNode* invertTree(TreeNode* root){if(root == NULL)return NULL;vector<TreeNode*> stack;stack.push_back(root);while(!stack.empty()){TreeNode* node = stack.back();stack.pop_back();swap(node->left,node->right);if(node->left)stack.push_back(node->left);if(node->right)stack.push_back(node->right);}return root;}
python：
def invertTree(self, root):if root:root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)return rootMaybe make it four lines for better readability:def invertTree(self, root):if root:invert = self.invertTreeroot.left, root.right = invert(root.right), invert(root.left)return root——————————————————————————–And an iterative version using my own stack:def invertTree(self, root):stack = [root]while stack:node = stack.pop()if node:node.left, node.right = node.right, node.leftstack += node.left, node.rightreturn root
def invertTree(self, root):if root is None:return Noneroot.left, root.right = self.invertTree(root.right), self.invertTree(root.left)return root
python非递归解决方案：
DFS version:def invertTree(self, root):if (root):self.invertTree(root.left)self.invertTree(root.right)root.left, root.right = root.right, root.leftreturn rootBFS version:def bfs_invertTree(self, root):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.leftreturn root
，将会错过更好的风景，保持一份平和，保持一份清醒。
