代码随想录day17| 二叉树的最大深度 二叉树的最小深度 完全二叉树的节点个数

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

分析 层序遍历 每层depth++

class Solution {
    public int maxDepth(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        if(root==null) return 0;
        deque.offer(root);
        int res=0;
        while(!deque.isEmpty()){
            int len=deque.size();
            res++;
            while(len-->0){
                TreeNode temp = deque.poll();
                if(temp.left!=null) deque.offer(temp.left);
                if(temp.right!=null) deque.offer(temp.right);
            }
        }

        return res;
        
    }
}
//递归写法
class Solution {
    public int maxDepth(TreeNode root) {
        return max(root);
    }

    public int max(TreeNode root){
        if(root==null) return 0;

        int left = max(root.left)+1;
        int right = max(root.right)+1;

        return Math.max(left,right);
    }
}

二叉树的最小深度

给定一个二叉树，找出其最小深度。

分析 层序遍历 如果左右节点==null 说明可以return depth

class Solution {
    public int minDepth(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        if(root==null) return 0;
        deque.offer(root);
        int depth=0;
        while(!deque.isEmpty()){
            int len=deque.size();
            depth++;
            while(len-->0){
                TreeNode temp= deque.poll();
                if(temp.left==null&&temp.right==null)   return depth;
                if(temp.left!=null) deque.offer(temp.left);
                if(temp.right!=null) deque.offer(temp.right);
            }
        }


        return depth;
    }

完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

分析 遍历时 count++

//递归写法
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;
        Deque<TreeNode> deque=new LinkedList<>();
        deque.offer(root);
        int count=0;
        while(!deque.isEmpty()){
            int len = deque.size();
            while(len-->0){
                TreeNode temp=deque.poll();
                count++;
                if(temp.left!=null) deque.offer(temp.left);
                if(temp.right!=null) deque.offer(temp.right);
            }
        }
        return count;
    }
}