day16 104,222

104. 二叉树的最大深度

class Solution {   //层序遍历
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> que=new LinkedList<>();
        que.offer(root);
        int dep=0;      //dep  记录深度
        while(!que.isEmpty()){
            int len=que.size();
            while(len>0){
                TreeNode tempNode=que.poll();
                if(len==1) dep++;   //等于1：遍历到本层最后一个节点   所以dep++；
                if(tempNode.left!=null) que.offer(tempNode.left);
                if(tempNode.right!=null) que.offer(tempNode.right);
                len--;
            }
        }
        return dep;
    }
}

//递归方法
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftLength=maxDepth(root.left);
        int rightLength=maxDepth(root.right);
        int dep=Math.max(leftLength,rightLength)+1;
        return dep;
    }
}

111. 二叉树的最小深度

//层序遍历
class Solution {
    public int minDepth(TreeNode root) {
        Queue<TreeNode> que=new LinkedList<TreeNode>();
        if(root==null){
            return 0;
        }
        que.offer(root);
        int curdep=1;
        while(!que.isEmpty()){
            
            int len=que.size();           
            while(len>0){
                TreeNode tempNode=que.poll();
                if(tempNode.left==null&&tempNode.right==null) return curdep;
                if(tempNode.left!=null){
                    que.offer(tempNode.left);
                }

                if(tempNode.right!=null){
                    que.offer(tempNode.right);
                }
                
                len--;
            }
            curdep++;
        }
        return 0;
    }
}

class Solution {
    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftLength=minDepth(root.left);
        int rightLength=minDepth(root.right);
        if(root.left==null&&root.right!=null) return rightLength+1;  //左空右不空 则找右
        if(root.right==null&&root.left!=null) return leftLength+1;	//右空左不空 找左          必须是两个子节点都是空才算
        return Math.min(leftLength,rightLength)+1;
        }
}

完全二叉树的节点个数

层序遍历写法
class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> que=new LinkedList<>();
        que.offer(root);
        int sum=0;
        while(!que.isEmpty()){
            int len=que.size();
            while(len>0){
                TreeNode tempNode=que.poll();
                sum++;           //每次poll时候记录一下   其他套模板
                if(tempNode.left!=null){
                    que.offer(tempNode.left);
                }
                if(tempNode.right!=null){
                    que.offer(tempNode.right);
                }
                len--;
            }
        }
        return sum;   
    }
}

递归方法

//这中递归是针对所有二叉树的方式，并没有利用到完全二叉树的特性，多消耗了内存
class Solution{
	public int countNodes(TreeNode root) {
		if(root==null) return 0;
		return countNodes(root.left)+countNodes(root.right)+1;
	}
}

针对完全二叉树的递归方法

class Solution{
	public int countNodes(TreeNode root) {
		if(root==null) return 0;
		int leftLength=0;
        TreeNode left=root.left;
        TreeNode right=root.right;
        int rightLength=0;
        while(left!=null){      //这两步是为了求左子树的左右的深度
            left=left.left;
            leftLength++;
        }
        while(right!=null){
            right=right.right;
            rightLength++;
        }
        if(rightLength==leftLength) return (2<<leftLength)-1;   //如果相等则这个子树是完全二叉数，直接用公式求出数量； 
		
        return countNodes(root.left)+countNodes(root.right)+1;    //递归根节点的左子树和右子树
    }
}