描述

操作给定的二叉树，将其变换为源二叉树的镜像。

思路1：广度优先遍历

使用栈

使用栈进行层序遍历：从左往右加入，弹出的时候变成从右往左。再交换左右节点

1. 8入栈
2. 弹出8。将6和10入栈
3. 交换6和10
4. 弹出10。将9和11入栈
5. 交换9和11
6. 弹出6。将5和7入栈
7. 交换5和7

public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null) {
            return pRoot;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(pRoot);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node.left != null) {
                stack.push(node.left);
            }
            if(node.right != null) {
                stack.push(node.right);
            }
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return pRoot;
    }
}

使用队列

也可以使用队列，从右往左入队，交换左右节点。

public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null) {
            return pRoot;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node.right != null) {
                queue.offer(node.right);
            }
            if(node.left != null) {
                queue.offer(node.left);
            }
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return pRoot;
    }
}

思路2：深度优先遍历

本质是访问每个节点，然后交换左右节点，因此二叉树的多种遍历方式都可以实现。

深度优先遍历：递归左子树和右子树，交换左右子树。

前序遍历

public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null) {
            return null;
        }
        //交换左右子树
        TreeNode tmp = pRoot.right;
        pRoot.right = pRoot.left;
        pRoot.left = tmp;
        //递归左右子树
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }
}

后序遍历

public class Solution {
    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;
    }
}

中序遍历

递归左子树和右子树，再交换父节点的左右节点

public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null) {
            return null;
        }
        Mirror(pRoot.left);
        //交换左右节点
        TreeNode tmp = pRoot.right;
        pRoot.right = pRoot.left;
        pRoot.left = tmp;
        //由于左右节点已经交换，因此这里传入的还是左节点
        Mirror(pRoot.left);
        return pRoot;
    }
}

思路3：递归重建二叉树

新建一棵二叉树B，递归遍历树A

public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null) {
            return null;
        }
        TreeNode ret = new TreeNode(pRoot.val);
        dfs(pRoot, ret);
        return ret;
    }
    void dfs(TreeNode node1, TreeNode node2) {
        if(node1 == null) {
            return;
        }
        if(node1.right != null) {
            node2.left = new TreeNode(node1.right.val);
        }
        if(node1.left != null) {
            node2.right = new TreeNode(node1.left.val);
        }
        dfs(node1.left, node2.right);
        dfs(node1.right, node2.left);
    }
}