剑指offer-18、⼆叉树的镜像
<h2 id="题描述">题⽬描述</h2><p>操作给定的⼆叉树，将其变换为源⼆叉树的镜像。</p>
<p>⼆叉树的镜像定义：源⼆叉树</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503291238522.jpeg" alt="" loading="lazy"></p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="递归">递归</h3>
<p>采用后序遍历（左-右-根）的方式递归访问每个节点：</p>
<ol>
<li>递归处理左子树</li>
<li>递归处理右子树</li>
<li>访问根节点并交换其左右子树</li>
</ol>
<pre><code class="language-java">public TreeNode mirrorTree(TreeNode root) {
if (root == null) return null;
// 先递归处理子树
TreeNode left = mirrorTree(root.left);
TreeNode right = mirrorTree(root.right);
// 再交换左右子树
root.left = right;
root.right = left;
return root;
}
</code></pre>
<p>或者采用前序遍历（根-左-右）的方式递归访问每个节点：</p>
<ol>
<li>访问根节点并交换其左右子树</li>
<li>递归处理左子树</li>
<li>递归处理右子树</li>
</ol>
<pre><code class="language-java">public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
// 交换左右子树
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 递归处理左右子树
mirrorTree(root.left);
mirrorTree(root.right);
return root;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，每个节点只被访问一次</li>
<li><strong>空间复杂度</strong>：O(h)，h为树的高度，递归栈空间消耗</li>
</ul>
<h3 id="迭代">迭代</h3>
<p>利用队列实现广度优先搜索(BFS)：</p>
<ol>
<li>将根节点加入队列</li>
<li>取出队首节点并交换其左右子树</li>
<li>将非空的左右子节点加入队列</li>
<li>重复直到队列为空</li>
</ol>
<pre><code class="language-java">public TreeNode mirrorTree(TreeNode root) {
if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// 交换左右子树
swap(node);
// 将子节点加入队列
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return root;
}
public void swap(TreeNode root) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)</li>
<li><strong>空间复杂度</strong>：O(n)，最坏情况下需要存储所有节点</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19019113
頁:
[1]