# 0226. 翻轉二叉樹 ## 題目地址(226. 翻轉二叉樹) <https://leetcode-cn.com/problems/invert-binary-tree/> ## 題目描述 ``` <pre class="calibre18">``` 翻轉一棵二叉樹。 示例： 輸入： 4 / \ 2 7 / \ / \ 1 3 6 9 輸出： 4 / \ 7 2 / \ / \ 9 6 3 1 備注: 這個問題是受到 Max Howell 的 原問題 啟發的 ： 谷歌：我們90％的工程師使用您編寫的軟件(Homebrew)，但是您卻無法在面試時在白板上寫出翻轉二叉樹這道題，這太糟糕了。 ``` ``` ## 前置知識 - [遞歸](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 遍歷樹（隨便怎么遍歷），然后將左右子樹交換位置。 ## 關鍵點解析 - 遞歸簡化操作 - 如果樹很高，建議使用棧來代替遞歸 - 這道題目對順序沒要求的，因此隊列數組操作都是一樣的，無任何區別 ## 代碼 - 語言支持：JS，Python，C++ Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */</span> <span class="hljs-title">/** * @param {TreeNode} root * @return {TreeNode} */</span> <span class="hljs-keyword">var</span> invertTree = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">root</span>) </span>{ <span class="hljs-keyword">if</span> (!root) <span class="hljs-keyword">return</span> root; <span class="hljs-title">// 遞歸</span> <span class="hljs-title">// const left = root.left;</span> <span class="hljs-title">// const right = root.right;</span> <span class="hljs-title">// root.right = invertTree(left);</span> <span class="hljs-title">// root.left = invertTree(right);</span> <span class="hljs-title">// 我們用stack來模擬遞歸</span> <span class="hljs-title">// 本質上遞歸是利用了執行棧，執行棧也是一種棧</span> <span class="hljs-title">// 其實這里使用隊列也是一樣的，因為這里順序不重要</span> <span class="hljs-keyword">const</span> stack = [root]; <span class="hljs-keyword">let</span> current = <span class="hljs-params">null</span>; <span class="hljs-keyword">while</span> ((current = stack.shift())) { <span class="hljs-keyword">const</span> left = current.left; <span class="hljs-keyword">const</span> right = current.right; current.right = left; current.left = right; <span class="hljs-keyword">if</span> (left) { stack.push(left); } <span class="hljs-keyword">if</span> (right) { stack.push(right); } } <span class="hljs-keyword">return</span> root; }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># Definition for a binary tree node.</span> <span class="hljs-title"># class TreeNode:</span> <span class="hljs-title"># def __init__(self, x):</span> <span class="hljs-title"># self.val = x</span> <span class="hljs-title"># self.left = None</span> <span class="hljs-title"># self.right = None</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">invertTree</span><span class="hljs-params">(self, root: TreeNode)</span> -> TreeNode:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root: <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span> stack = [root] <span class="hljs-keyword">while</span> stack: node = stack.pop(<span class="hljs-params">0</span>) node.left, node.right = node.right, node.left <span class="hljs-keyword">if</span> node.left: stack.append(node.left) <span class="hljs-keyword">if</span> node.right: stack.append(node.right) <span class="hljs-keyword">return</span> root ``` ``` C++ Code： ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function">TreeNode* <span class="hljs-title">invertTree</span><span class="hljs-params">(TreeNode* root)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-params">NULL</span>) <span class="hljs-keyword">return</span> root; <span class="hljs-keyword">auto</span> q = <span class="hljs-params">queue</span><TreeNode*>(); q.push(root); <span class="hljs-keyword">while</span> (!q.empty()) { <span class="hljs-keyword">auto</span> n = q.front(); q.pop(); swap(n->left, n->right); <span class="hljs-keyword">if</span> (n->left != <span class="hljs-params">nullptr</span>) { q.push(n->left); } <span class="hljs-keyword">if</span> (n->right != <span class="hljs-params">nullptr</span>) { q.push(n->right); } } <span class="hljs-keyword">return</span> root; } }; ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。