226. 翻转二叉树

栈也可以、队列也可以，能够遍历整个二叉树就可以把它们交换

栈的方法

class Solution {
    public TreeNode invertTree(TreeNode root) {
        
    	TreeNode newtree = root;
    	if(root==null)
    		return root;
    	Stack<TreeNode> newstack = new Stack();
    	newstack.push(root);
    	while(!newstack.isEmpty()){
    		newtree = newstack.pop();
    		if(newtree.left!=null&&newtree.right!=null){
    			TreeNode temp = newtree.left;
    			newtree.left = newtree.right;
    			newtree.right = temp;
    			newstack.push(newtree.left);
    			newstack.push(newtree.right);    			
    		}
    		else if(newtree.left==null&&newtree.right!=null){
    			TreeNode temp = newtree.left;
    			newtree.left = newtree.right;
    			newtree.right = temp;
    			newstack.push(newtree.left);
    		}
    		else if(newtree.left!=null&&newtree.right==null){
    			TreeNode temp = newtree.left;
    			newtree.left = newtree.right;
    			newtree.right = temp;
    			newstack.push(newtree.right);
    		}
    	}
    	return root;
    }
}

第一次成功递归：

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

递归三要素：1、出口条件  2、初始条件  3、由n到n+1和由n+1返回n