# 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啦。 关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。