226.invert-binary-tree.md

题目地址(226. 翻转二叉树)

https://leetcode-cn.com/problems/invert-binary-tree/

题目描述

翻转一棵二叉树。 示例： 输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / \ 7 2 / \ / \ 9 6 3 1 备注: 这个问题是受到 Max Howell 的 原问题 启发的 ： 谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。 

前置知识

• 递归

公司

• 阿里
• 腾讯
• 百度
• 字节

思路

这是一个经典的面试问题，难度不大，大家可以用它练习一下递归和迭代。

算法：

遍历树（随便怎么遍历），然后将左右子树交换位置。

关键点解析

• 递归简化操作
• 如果树很高，建议使用栈来代替递归
• 这道题目对顺序没要求的，因此队列数组操作都是一样的，无任何区别

代码

• 语言支持：JS，Python，C++

Javascript Code:

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {TreeNode} */varinvertTree=function(root){if(!root)returnroot;// 递归// const left = root.left;// const right = root.right;// root.right = invertTree(left);// root.left = invertTree(right);// 我们用stack来模拟递归// 本质上递归是利用了执行栈，执行栈也是一种栈// 其实这里使用队列也是一样的，因为这里顺序不重要conststack=[root];letcurrent=null;while((current=stack.shift())){constleft=current.left;constright=current.right;current.right=left;current.left=right;if(left){stack.push(left);}if(right){stack.push(right);}}returnroot;};

Python Code:

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: definvertTree(self, root: TreeNode) ->TreeNode: ifnotroot: returnNonestack= [root] whilestack: node=stack.pop(0) node.left, node.right=node.right, node.leftifnode.left: stack.append(node.left) ifnode.right: stack.append(node.right) returnroot

C++ Code：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * };*/classSolution { public: TreeNode* invertTree(TreeNode* root) { if (root == NULL) return root; auto q = queue<TreeNode*>(); q.push(root); while (!q.empty()) { auto n = q.front(); q.pop(); swap(n->left, n->right); if (n->left != nullptr) { q.push(n->left); } if (n->right != nullptr) { q.push(n->right); } } return root; } };

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

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