树与图简单2 种解法
#226翻转二叉树
交换二叉树每个节点的左右子树。
#二叉树#深度优先搜索#广度优先搜索
原题
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3] 输出：[2,3,1]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
解题主线
- 每个节点恰好执行一次左右指针交换。
解法 1：递归翻转
递归翻转左右子树，再交换其返回值。
-
时间复杂度： O(n)
-
空间复杂度： O(h)
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
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;
}
}解法 2：BFS 翻转
队列遍历每个节点并原地交换左右孩子。
-
时间复杂度： O(n)
-
空间复杂度： O(w)
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// 每个出队节点恰好交换一次左右指针
TreeNode temporary = node.left;
node.left = node.right;
node.right = temporary;
// 交换后入队的是新左右孩子，但仍覆盖原来的两棵子树
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return root;
}
}边界与易错点
- 递归时应明确使用递归返回的已翻转子树，避免交换后引用混乱。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q226_invertTree.java