目錄：
1.Invert Binary Tree - 二叉樹翻轉 [遞歸]


題目概述：

Invert a binary tree.

4/ \2 7/ \ / \ 1 3 6 9 to 4/ \7 2/ \ / \ 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.

題目分析：
? ? ? ? 題目背景是MaxHowell(他是蘋果電腦最受歡迎的homebrew程序作者)去Google面試，面試官說：“雖然在Google有90%的工程師用你寫的Homebrew，但是你居然不能再白板上寫出翻轉二叉樹的代碼，所以滾帶吧”！
? ? ? ? 該題最初想法就是通過遞歸依次交換左右結點，但是想得太多，如“是否需要再建一顆樹”、“是否需要引入隊列或BFS”，最終沒有AC。

我的代碼：

/*** 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 *left, *right;if(root==NULL)return root;left = root->left;right = root->right;root->left = invertTree(right);root->right = invertTree(left);return root;} };

其他代碼：
? ? ? ? 推薦閱讀和采用二叉樹非遞歸層次遍歷算法實現如下。
? ? ? ??你會翻轉二叉樹嗎？--談程序員的招聘
? ? ? ? http://blog.csdn.net/sunao2002002/article/details/46482559

//第二種方法 通過隊列層次遍歷隊列實現 class Solution { public:TreeNode* invertTree(TreeNode* root) {queue<TreeNode*> q;if(root==NULL)return root;q.push(root);int size=q.size();while(size>0){TreeNode *p=q.front();q.pop();//交換左右結點TreeNode *LNode=p->left;TreeNode *RNode=p->right;p->left=RNode;p->right=LNode;//進入隊列if(p->left) {q.push(p->left);}if(p->right) {q.push(p->right);}size=q.size();}return root;} };

其他題目：

(By:Eastmount 2015-9-12 凌晨5點半? ?http://blog.csdn.net/eastmount/)

總結

以上是生活随笔為你收集整理的[LeetCode] Invert Binary Tree - 二叉树翻转系列问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。