【递归】二叉树的镜像

求解代码

这道题遍历二叉树的每一个节点，然后交换左右子节点就可以了。

1.前序遍历

publicTreeNodeMirror(TreeNodepRoot){if(pRoot==null){returnnull;}TreeNodetemp=pRoot.left;pRoot.left=pRoot.right;pRoot.right=temp;Mirror(pRoot.left);Mirror(pRoot.right);returnpRoot;}

2.中序遍历

publicTreeNodeMirror(TreeNodepRoot){if(pRoot==null){returnnull;}Mirror(pRoot.left);TreeNodetemp=pRoot.left;pRoot.left=pRoot.right;pRoot.right=temp;Mirror(pRoot.left);//注意上面交换过了returnpRoot;}

3.后序遍历

publicTreeNodeMirror(TreeNodepRoot){if(pRoot==null){returnnull;}TreeNodeleft=Mirror(pRoot.left);TreeNoderight=Mirror(pRoot.right);pRoot.left=right;pRoot.right=left;returnpRoot;}

注意⚠️：

这里解释一下中序遍历的第二个递归为什么是Mirror(pRoot.left);而不是Mirror(pRoot.right);?

因为执行完：

TreeNodetemp=pRoot.left;pRoot.left=pRoot.right;pRoot.right=temp;

这三行代码之后，当前节点的左右指针发生了互换，指向变成了：

pRoot.left → 原右子树(R)pRoot.right → 原左子树(L)

要处理的「原右子树 R」，现在的内存地址其实是pRoot.left，

如果此时写Mirror(pRoot.right)，实际处理的是「已经翻转完的原左子树 L」，这样就会造成翻转结果错误。