0226. 翻转二叉树
题目地址(226. 翻转二叉树)
题目描述
1
翻转一棵二叉树。
2
3
示例：
4
5
输入：
6
7
4
8
/ \
9
2 7
10
/ \ / \
11
1 3 6 9
12
输出：
13
14
4
15
/ \
16
7 2
17
/ \ / \
18
9 6 3 1
19
备注:
20
这个问题是受到 Max Howell 的 原问题 启发的 ：
21
22
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
Copied!
前置知识
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
这是一个经典的面试问题，难度不大，大家可以用它练习一下递归和迭代。
算法：
遍历树（随便怎么遍历），然后将左右子树交换位置。
关键点解析
- 递归简化操作
- 如果树很高，建议使用栈来代替递归
- 这道题目对顺序没要求的，因此队列数组操作都是一样的，无任何区别
代码
- 语言支持：JS，Python，C++
Javascript Code:
1
/**
2
* Definition for a binary tree node.
3
* function TreeNode(val) {
4
* this.val = val;
5
* this.left = this.right = null;
6
* }
7
*/
8
/**
9
* @param {TreeNode} root
10
* @return {TreeNode}
11
*/
12
var invertTree = function (root) {
13
if (!root) return root;
14
// 递归
15
// const left = root.left;
16
// const right = root.right;
17
// root.right = invertTree(left);
18
// root.left = invertTree(right);
19
// 我们用stack来模拟递归
20
// 本质上递归是利用了执行栈，执行栈也是一种栈
21
// 其实这里使用队列也是一样的，因为这里顺序不重要
22
23
const stack = [root];
24
let current = null;
25
while ((current = stack.shift())) {
26
const left = current.left;
27
const right = current.right;
28
current.right = left;
29
current.left = right;
30
if (left) {
31
stack.push(left);
32
}
33
if (right) {
34
stack.push(right);
35
}
36
}
37
return root;
38
};
Copied!
Python Code:
1
# Definition for a binary tree node.
2
# class TreeNode:
3
# def __init__(self, x):
4
# self.val = x
5
# self.left = None
6
# self.right = None
7
8
class Solution:
9
def invertTree(self, root: TreeNode) -> TreeNode:
10
if not root:
11
return None
12
stack = [root]
13
while stack:
14
node = stack.pop(0)
15
node.left, node.right = node.right, node.left
16
if node.left:
17
stack.append(node.left)
18
if node.right:
19
stack.append(node.right)
20
return root
Copied!
C++ Code：
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
public:
12
TreeNode* invertTree(TreeNode* root) {
13
if (root == NULL) return root;
14
auto q = queue<TreeNode*>();
15
q.push(root);
16
while (!q.empty()) {
17
auto n = q.front(); q.pop();
18
swap(n->left, n->right);
19
if (n->left != nullptr) {
20
q.push(n->left);
21
}
22
if (n->right != nullptr) {
23
q.push(n->right);
24
}
25
}
26
return root;
27
}
28
};
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago