二叉树的镜像

/**
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){
            return;
        }
        helper(root);
    }
    public TreeNode helper(TreeNode root){
        if(root==null){
            return null;
        }
        TreeNode rootTemp = root;
        TreeNode left = helper(root.right);
        TreeNode right = helper(root.left);
        rootTemp.left = left;
        rootTemp.right = right;
        return rootTemp; 
    }
}

 

问题

翻转一棵二叉树。

示例：

输入：

     4

   /   \

  2     7

 / \   / \

1   3 6   9

输出：

     4

   /   \

  7     2

 / \   / \

9   6 3   1

思路

先交换根节点的两个子结点之后，我们注意到值为10、6的结点的子结点仍然保持不变，因此我们还需要交换这两个结点的左右子结点。做完这两次交换之后，我们已经遍历完所有的非叶结点。此时变换之后的树刚好就是原始树的镜像。交换示意图如下所示：

递归

public static TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode right = invertTree(root.right);
    TreeNode left = invertTree(root.left);
    root.left = right;
    root.right = left;
    return root;
}

迭代

public static TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        TreeNode temp = current.left;
        current.left = current.right;
        current.right = temp;
        if (current.left != null) {
            queue.add(current.left);
        }
        if (current.right != null) {
            queue.add(current.right);
        }
    }
    return root;
}