import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
     *
     * 
     * @param pRoot TreeNode類 
     * @return TreeNode類
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        //空樹
        if(pRoot == null)  
            return null;
        //輔助棧
        Stack<TreeNode> s = new Stack<TreeNode>(); 
        //根節(jié)點先進棧
        s.push(pRoot); 
        while (!s.isEmpty()){ 
            TreeNode node = s.pop();
            //左右節(jié)點入棧
            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;


        /*
         //空樹返回
        if(pRoot == null) 
            return null;
        //先遞歸子樹
        TreeNode left = Mirror(pRoot.left);  
        TreeNode right = Mirror(pRoot.right);
        //交換 
        pRoot.left = right; 
        pRoot.right = left;
        return pRoot;
        */
    }
}

27在55的基礎上對二叉樹進行操作

01：思路：

因為我們需要將二叉樹鏡像，意味著每個左右子樹都會交換位置，如果我們從上到下對遍歷到的節(jié)點交換位置，但是它們后面的節(jié)點無法跟著他們一起被交換，因此我們可以考慮自底向上對每兩個相對位置的節(jié)點交換位置，這樣往上各個子樹也會被交換位置。

自底向上的遍歷方式，我們可以采用后序遞歸的方法。

具體做法：

• step 1：先深度最左端的節(jié)點，遇到空樹返回，處理最左端的兩個子節(jié)點交換位置。
• step 2：然后進入右子樹，繼續(xù)按照先左后右再回中的方式訪問。
• step 3：再返回到父問題，交換父問題兩個子節(jié)點的值。

02：思路：

二叉樹中能夠用遞歸的，我們大多也可以用棧來實現(xiàn)。棧的訪問是一種自頂向下的訪問，因此我們需要在左右子節(jié)點入棧后直接交換，然后再訪問后續(xù)棧中內容。

具體做法：

• step 1：優(yōu)先檢查空樹的情況。
• step 2：使用棧輔助遍歷二叉樹，根節(jié)點先進棧。
• step 3：遍歷過程中每次彈出棧中一個元素，然后該節(jié)點左右節(jié)點分別入棧。
• step 4：同時我們交換入棧兩個子節(jié)點的值，因為子節(jié)點已經(jīng)入棧了再交換，就不怕后續(xù)沒有交換。