剑指offer - 二叉树镜像(Java实现)

题目链接：https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&&tqId=11171&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：递归。我们可以交换根节点的左右儿子，然后向左儿子和右儿子递归，按照交换规则继续交换即可。递归出口：根节点为空。

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) {
            return ;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        Mirror(root.left);
        Mirror(root.right);
    }
}

  思路二：层序遍历，按照层将结点放入队列中，然后从队列依次取，取出时交换其左右儿子即可。

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null) return ;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(q.size() > 0) {
            TreeNode cur = q.poll();
            if(cur.left != null) q.add(cur.left);
            if(cur.right != null) q.add(cur.right);
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
        }
    }
}