知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 03 - 翻转二叉树 ## 题目(LeetCode 226) 翻转一棵二叉树(镜像翻转)。 ``` 输入: 输出: 4 4 / \ / \ 2 7 7 2 / \ / \ / \ / \ 1 3 6 9 9 6 3 1 ``` ## 大白话理解 把树照镜子。每个节点的左孩子和右孩子互换位置就行了。 想象你站在每个节点面前,把它的左手和右手交换。从上到下每个节点都做一次交换,整棵树就翻转了。 ``` 第 1 步:交换根节点的左右孩子 4 4 / \ → / \ 2 7 7 2 第 2 步:递归交换子树 7 的左右孩子交换:6↔9 2 的左右孩子交换:1↔3 最终: 4 / \ 7 2 / \ / \ 9 6 3 1 ``` ## 代码 ```java public TreeNode invertTree(TreeNode root) { if (root == null) return null; // 交换左右子节点 TreeNode temp = root.left; root.left = root.right; root.right = temp; // 递归翻转左右子树 invertTree(root.left); invertTree(root.right); return root; } ``` ### 更简洁的写法 ```java public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode left = invertTree(root.left); // 翻转左子树 TreeNode right = invertTree(root.right); // 翻转右子树 root.left = right; // 交换 root.right = left; return root; } ``` 两种写法的区别:第一种是先交换再递归(前序),第二种是先递归再交换(后序)。都能得到正确结果,因为每个节点都会被交换一次。 ## 为什么这样就对了? ``` 翻转一棵树 = 交换当前节点的左右孩子 + 翻转左子树 + 翻转右子树 这是一个递归定义: 翻转整棵树 → 翻转子树 → 翻转子子树 → ... → 叶子节点(没有孩子,不用交换) ``` ## BFS 写法 ```java public TreeNode invertTree(TreeNode root) { if (root == null) return null; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); // 交换左右 TreeNode temp = node.left; node.left = node.right; node.right = temp; if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } return root; } ``` 层序遍历,每个节点都交换一下左右孩子。 ## 复杂度 - 时间:O(n) - 空间:O(h),递归栈深度 ## 一句话总结 每个节点交换左右孩子,递归处理所有节点。 --- 上一篇:[02 - 二叉树的最大深度](./02-max-depth.md) | 下一篇:[04 - 对称二叉树](./04-symmetric-tree.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入