递归-二叉树的镜像

在这里插入图片描述

求解代码

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

1.前序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


   public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot==null){
			return null;
		}

		TreeNode temp = pRoot.left;
		pRoot.left = pRoot.right;
		pRoot.right = temp;

		Mirror(pRoot.left);
		Mirror(pRoot.right);

		return pRoot;
    }

2.中序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot==null){
			return null;
		}


		Mirror(pRoot.left);

		TreeNode temp = pRoot.left;
		pRoot.left = pRoot.right;
		pRoot.right = temp;



		Mirror(pRoot.left);//注意上面交换过了

		return pRoot;
    }

3.后序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot==null){
			return null;
		}

		TreeNode left = Mirror(pRoot.left);
		TreeNode right = Mirror(pRoot.right);

		pRoot.left = right;
		pRoot.right = left;

		return pRoot;
    }

注意⚠️：

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

因为执行完：

1
2
3


		TreeNode temp = pRoot.left;
		pRoot.left = pRoot.right;
		pRoot.right = temp;

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

1
2


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

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

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