题目：求一棵二叉树的镜像

思路：破坏原有的二叉树   不破坏原有二叉树，新建一个新的二叉树

递归：破坏原有的二叉树

　　public static TreeNode mirror(TreeNode root){        if(root == null)            return null;        TreeNode left = mirror(root.left);        TreeNode right = mirror(root.right);        root.left = right;        root.right = left;        return root;　　//每次返回到上一个节点    }

递归：不破坏原有的二叉树

public static TreeNode newMirror(TreeNode root){        if(root == null)            return null;        TreeNode node = new TreeNode(root.val);        node.left = newMirror(root.right);        node.right = newMirror(root.left);        return node;    }

 迭代：破坏原来的二叉树

public static void mirrorDestroy(TreeNode root){        if(root == null)            return;          Stack
     
       stack = new Stack
      
       ();          stack.push(root);          while(!stack.isEmpty()){              TreeNode cur = stack.pop();                            TreeNode tmp  = cur.right;              cur.right = cur.left;              cur.left = tmp;                            if(cur.left != null){                  stack.push(cur.left);              }              if(cur.right != null){                  stack.push(cur.right);              }          }    }
      
     

迭代：不破坏原来的二叉树

public static TreeNode mirrorUndestory(TreeNode root){        if(root == null)            return null;        Stack
     
       stack = new Stack
      
       ();        Stack
       
         newStack = new Stack
        
         ();        stack.push(root);                TreeNode newRoot = new TreeNode(root.val);        newStack.push(newRoot);                while(!stack.isEmpty()){            TreeNode cur = stack.pop();            TreeNode newCur = newStack.pop();                        if(cur.right != null){                stack.push(cur.right);                newCur.left = new TreeNode(cur.right.val);                newStack.push(newCur.left);            }            if(cur.left != null){                stack.push(cur.left);                newCur.right = new TreeNode(cur.left.val);                newStack.push(newCur.right);            }        }        return newRoot;    }