BM33 题解 | #二叉树的镜像#

阿哈时刻：

知道为什么改变TreeNode.val 无效了！答案里面实现镜像的方法是改变引用，而我刚开始则是期望通过改变值，来实现二叉树镜像反转的功能，但是，现实情况是，有些二叉树根本就不是我想的那种节点很全的那种，总有些缺胳膊断腿的，那种你通过改变值val当然是无效的，只能改变地址引用，来实现二叉树镜像功能了！

递归遍历，二叉树过程中，可以做的改变很多，无论二叉树是否中途，有没有返回值，要理解的是，递归的本质，即是：

如果是后序遍历，遍历顺序，一定是先从左右根，而且是从下到上，从左到右，再到root节点到。

那二叉树镜像反转的递归，依旧逃不出这个顺序和过程，只是，我们可以在这个过程中中途可以做很多手脚，

改变值，交互值等等都是可以的。所以，二叉树镜像反转的过程，画个图是这样的：

解题思路：

1、递归的方法，二叉树的后序遍历，就跟之前的，后序遍历一摸一样的：

void postOrderTree(TreeNode root){
    if(root == null) return;
    postOrderTree(root.left);
    postOrderTree(root.right);
    print("val:" + root.val);
}

具体有个区别，就是可以返回值，这带来了很大的改变，递归的过程一样，只是有返回值，还有可以操作。

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

        TreeNode left = Mirror(pRoot.left); //1. 后序遍历左子节点
        TreeNode right = Mirror(pRoot.right); //2. 后序遍历左子节点

        //3. visit t，操作目标节点
        pRoot.left = right;
        pRoot.right = left;
        return pRoot;
    }

import java.util.*;

public class Solution {
    /**
     * 递归方法，改变二叉树
     * @param pRoot TreeNode类
     * @return TreeNode类
     */
    
    // 本质上是一种二叉树的后续遍历
    // 这个比较特别的是可以返回值
    // 中途也可以对值做交换
    // 跟之前的二叉搜索树变双向链表很像
    public TreeNode Mirror2 (TreeNode pRoot) {
        if (pRoot == null) {
            return null;
        }

        TreeNode left = Mirror(pRoot.left); //1. 后序遍历左子节点
        TreeNode right = Mirror(pRoot.right); //2. 后序遍历左子节点

        //3. visit t，操作目标节点
        pRoot.left = right;
        pRoot.right = left;
        return pRoot;
    }

	/**
	 * 使用栈方法，遍历过程中改变二叉树
	 */
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null) {
            return null;
        }
        Stack<TreeNode> s = new Stack<>();
        s.push(pRoot);
        while(!s.isEmpty()) {
            TreeNode node = s.pop();
            if(node.left!=null) {
                s.push(node.left);
            }
            if(node.right!=null) {
                s.push(node.right);
            }
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
        return pRoot;
    }
   
}