[劍指offer] 二叉樹的鏡像

題目描述

操作給定的二叉樹，将其變換為源二叉樹的鏡像。

輸入描述:

二叉樹的鏡像定義：
           

源二叉樹 
        8
       /  \
      6   10
     / \  / \
    5  7 9 11
    鏡像二叉樹
        8
       /  \
      10   6
     / \  / \
    11 9 7  5
           

解題思路

通過對以上兩棵樹的觀察，我們可以總結出這兩棵樹的根節點相同，但它們的左、右兩個子節點交換了位置。是以我們可以得出求一棵樹的鏡像的過程：先前序周遊這棵樹的每個節點，如果周遊到的節點有子節點，就交換它的兩個子節點。當交換完所有非葉節點的左、右子節點之後，就得到了樹的鏡像。

參考代碼

/**
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;
        //目前節點沒有葉子節點，直接傳回
        if(root.left == null && root.right == null)
            return;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        //遞歸交換葉子節點
        if(root.left != null)
            Mirror(root.left);
        if(root.right != null)
            Mirror(root.right);
    }
}