翻转二叉树
# 📃 题目描述
题目链接:
- 剑指 Offer 27. 二叉树的镜像 (opens new window)
- 226. 翻转二叉树 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
翻转一棵二叉树。
示例:
输入:
4
/ \
2 7
/ \ / \
1 3 6 9
输出:
4
/ \
7 2
/ \ / \
9 6 3 1
# 🔔 解题思路
所谓翻转,就是把每个节点的左右孩子交换一下就行了。
所以思路很简单,在遍历二叉树的过程中,去翻转每一个节点的左右孩子就可以达到整体翻转的效果。
总共四种遍历方式,除了中序遍历(中序遍历会把某些节点的左右孩子翻转了两次),其余三种方式都是可以的
以先序遍历为例:

class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
if (root.left == null && root.right == null) {
return root;
}
// 先翻转根节点的左右孩子
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 再翻转左孩子的左右孩子
invertTree(root.left);
// 再翻转右孩子的左右孩子
invertTree(root.right);
return root;
}
}
再来波先序遍历的迭代法:
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
if (root.left == null && root.right == null) {
return root;
}
// 辅助栈
Stack<TreeNode> stack = new Stack<>();
// 工作指针
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.push(cur);
// 交换该节点的左右孩子
TreeNode temp = cur.left;
cur.left = cur.right;
cur.right = temp;
cur = cur.left;
} else {
cur = stack.pop();
cur = cur.right;
}
}
return root;
}
}
是不是很简单,其实就是把先序遍历中,将某个节点加入结果集 res 的那行代码,修改成了交换该节点的左右孩子
# 💥 复杂度分析
- 空间复杂度:O(LogN)
- 时间复杂度:O(N), 我们会遍历二叉树中的每一个节点,对每个节点而言,我们在常数时间内交换其两棵子树
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10