package easy;

public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	public TreeNode(int x) {
		val = x;
	}
	
	//树的深度
	public int maxDepth(TreeNode root) {
		 if(root == null) return 0;
		 else{
			 int depthLeft = maxDepth(root.left);
			 int depthRight = maxDepth(root.right);
			 return 1 + (depthLeft > depthRight ? depthLeft : depthRight);
		 }
	        
	 }
	
	//两个树是否相同
	public boolean isSameTree(TreeNode p, TreeNode q) {
		if(p==null && q == null) return true;
		if(p != null && q != null && p.val == q.val){
			return isSameTree(p.left, q.left)&& isSameTree(p.right, q.right);
		}
		return false;
			
    }
	
	//反转树
	public TreeNode invertTree(TreeNode root) {
		if(root == null) return null;
		TreeNode a = new TreeNode(root.val);
		a.right = invertTree(root.left);
		a.left =invertTree(root.right);
        return a;
    }
	
	//二分搜索树的最小公共祖先（一个节点是自己的子孙）
	//二分搜索树 某个节点的值大于它的左子树的所有值，小于右子树的所有值
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if(root == null || p == null || q ==null) return null;
		else if(root.val >= Math.min(p.val, q.val) && root.val <= Math.max(p.val, q.val)) return root;
		else if(root.val > p.val && root.val > q.val)  return lowestCommonAncestor(root.left, p, q);
		return lowestCommonAncestor(root.right, p, q);
    }
	
	/**
	 * Given a binary tree, determine if it is height-balanced.
	 * the depth of the two subtrees of every node never differ by more than 1. 
	 * @param root
	 * @return
	 */
	public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        if(Math.abs(maxDepth(root.left)-maxDepth(root.right)) > 1) return false;
        else return isBalanced(root.left)&& isBalanced(root.right); 
    }
	
	/**
	 * 树是否是镜像对称的
	 * @param root
	 * @return
	 */
	public boolean isSymmetric(TreeNode root) {
		//先反转树，然后比较反转后的树和原来的树是否为一样的
        if(root == null) return true;
        TreeNode other = invertTree(root);
        return isSameTree(root, other);
    }
	
}

@@ -10,16 +10,96 @@
 asy;%0D%0A%0D%0A
+import java.util.ArrayList;%0D%0Aimport java.util.List;%0D%0Aimport java.util.Queue;%0D%0A%0D%0A
 public c
@@ -2120,11 +2120,899 @@
   %7D%0D%0A%09%0D%0A
+%09/**%0D%0A%09 * %E5%B1%82%E7%BA%A7%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91%0D%0A%09 * @param root%0D%0A%09 * @return%0D%0A%09 */%0D%0A%09public List%3CList%3CInteger%3E%3E levelOrderBottom(TreeNode root) %7B%0D%0A        List%3CList%3CInteger%3E%3E result = new ArrayList%3C%3E();%0D%0A        List%3CTreeNode%3E list = new ArrayList%3C%3E();%0D%0A        if(root == null) return result;%0D%0A        list.add(root);%0D%0A        int i = 1;%0D%0A        int j = 0;%0D%0A        while(!list.isEmpty())%7B%0D%0A        %09List%3CInteger%3E x = new ArrayList%3C%3E();%0D%0A        %09int nums_level = 0;%0D%0A        %09for(j=0;j%3Ci;j++)%7B%0D%0A        %09%09TreeNode temp = list.get(0);%0D%0A        %09%09list.remove(0);%0D%0A        %09%09x.add(temp.val);%0D%0A        %09%09if(temp.left!= null)%7B%0D%0A        %09%09%09nums_level++;%0D%0A        %09%09%09list.add(temp.left);%0D%0A        %09%09%7D%0D%0A        %09%09if(temp.right!= null)%7B%0D%0A        %09%09%09nums_level++;%0D%0A        %09%09%09list.add(temp.right);%0D%0A        %09%09%7D%0D%0A        %09%7D%0D%0A        %09result.add(0, x);%0D%0A        %09i=nums_level;%0D%0A        %7D%0D%0A        return result;%0D%0A    %7D%0D%0A%09%0D%0A%09%0D%0A
 %7D%0D%0A

add 分层遍历二叉树