0226. 翻转二叉树
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}
*/
var invertTree = function (root) {
if (!root) return root;
// 递归
// const left = root.left;
// const right = root.right;
// root.right = invertTree(left);
// root.left = invertTree(right);
// 我们用stack来模拟递归
// 本质上递归是利用了执行栈，执行栈也是一种栈
// 其实这里使用队列也是一样的，因为这里顺序不重要
const stack = [root];
let current = null;
while ((current = stack.shift())) {
const left = current.left;
const right = current.right;
current.right = left;
current.left = right;
if (left) {
stack.push(left);
}
if (right) {
stack.push(right);
}
}
return root;
};
Python Code:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
stack = [root]
while stack:
node = stack.pop(0)
node.left, node.right = node.right, node.left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return root
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) {}
* };
*/
class Solution {
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 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 4mo ago