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)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。