二叉树part03算法

二叉树part03

今日内容：

● 104.二叉树的最大深度 559.n叉树的最大深度
● 111.二叉树的最小深度
● 222.完全二叉树的节点个数

1.104.二叉树的最大深度

104.?二叉树的最大深度

111.?二叉树的最小深度

1.1思路1：层序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {

        //层数即是深度

         //定义一个二维数组，用作结果返回
        List<List<Integer>> result=new ArrayList<>();
        //定义一个队列
        Queue<TreeNode> queue=new LinkedList<>();
        //开始写遍历逻辑
        if(root!=null){
            //将根节点存进队列中
            queue.add(root);
        }
        //如果队列不为空
        while(!queue.isEmpty()){
            //记录下现在的值
            int size=queue.size();
            //定义一维数组
            List<Integer> arr=new ArrayList<>();
            //进行出列和把新的子节点入列
            while(size>0){
                size--;
                //将现在的队列顶部元素存储
                TreeNode node=queue.peek();
                //进行出列
                queue.poll();
                //将存储的节点值放进一维数组中
                arr.add(node.val);
                //继续将该节点的左右孩子添加进去
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
                //继续下一层循环
            }
            //将一维数组添加进二维数组中
            result.add(arr);
            //看二维数组中有多少层（多少个一维数组）一个一维数组代表一层
            // int depth=0;
            // for(int i=0;i<result.size();i++){

            // }
        }
        return result.size();

    }
}

1.2思路2：递归遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        //看完代码随想录后，递归遍历法
        //深度是到根节点的距离，高度是到叶子节点的距离
        //最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
        return getHeight(root);

    }
    //写一个求高度的遍历
    public int getHeight(TreeNode root){
       //如果根节点为空，那么整棵树的高度就是0
       if(root==null){
           return 0;
       }
       //开始遍历根节点的左右孩子节点
       //后序遍历，左右中
       int leftHeight=getHeight(root.left);
       int rightHeight=getHeight(root.right);
       int middle=1+Math.max(leftHeight,rightHeight);//根节点加上左右孩子树的高度
       return middle;
    }
}

2.111.二叉树的最小深度

2.1层序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        //  //定义一个二维数组，用作结果返回
        //List<Integer> result=new ArrayList<>();
        //定义一个队列
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){
            return 0;
        }
        //将根节点存进队列中
        queue.add(root);
        //定义深度
        int depth=0;

        //如果队列不为空
        while(!queue.isEmpty()){
            //记录下现在的值
            int size=queue.size();
            depth++;
            // //定义一维数组
            // List<Integer> arr=new ArrayList<>();
            TreeNode node=null;
            //进行出列和把新的子节点入列
            while(size>0){
                size--;
                //将现在的队列顶部元素存储
                node=queue.peek();
                //进行出列
                queue.poll();
                //如果当前左右孩子都为空的话，返回最小深度
                if(node.left==null&&node.right==null){
                    return depth;
                }
                //继续将该节点的左右孩子添加进去
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
                //继续下一层循环
            }
            //根节点只有1个，重新回到判断队列是否为空
            //此时将这一层的一维数组存进二维数组中
            //result.add(arr);
        }
        //return result;
        return depth;
       
    }
}

2.2递归遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        return getHeight(root);
    }
    //写一个求最小的遍历
    public int getHeight(TreeNode root){
       //如果根节点为空，那么整棵树的高度就是0
       if(root==null){
           return 0;
       }
       //开始遍历根节点的左右孩子节点
       //后序遍历，左右中
       int leftHeight=getHeight(root.left);
       int rightHeight=getHeight(root.right);
       if(root.left==null&&root.right!=null){
           return 1+rightHeight;
       }
       if(root.left!=null&&root.right==null){
           return 1+leftHeight;
       }
       int middle=1+Math.min(leftHeight,rightHeight);//根节点加上左右孩子树的高度
       return middle;
    }
}

3.222.完全二叉树的节点个数

222.?完全二叉树的节点个数

3.1思路1：层序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        //那不就是遍历到一个就入队列，然后存进数组中，看数组大小吗
        if(root==null){return 0;}
        //定义一个队列
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        //定义一个计数器
        int result=0;

        while(!queue.isEmpty()){
            //队列不为空，记录当前内存
            int size=queue.size();
            while(size>0){
                size--;
                //进行计数，出队列和人队列
                result++;
                TreeNode node=queue.poll();
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                } 
            }    
        }
        return result;
    }
    
}

3.2思路2：完全二叉树特性

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
				// 看完代码随想录的思路：用完全二叉树的特性做题
        // 遍历到满二叉树，能用满二叉树的节点公式2的n次方（深度）-1，将这个结果返回给父节点
        // 父节点到最后一起算节点和
        return getNum(root);
    }
    //递归
    public int getNum(TreeNode root){
        //第一种终止条件
        if(root==null){
            return 0;
        }
        //第二种终止条件是遍历到满二叉树，返回节点数值给上一层
        TreeNode left=root.left;
        TreeNode right=root.right;
        //左子树的深度
        int leftDepth=0;
        //右子树深度
        int rightDepth=0;
        //左侧遍历
        while(left!=null){
            left=left.left;
            leftDepth++;
        }
        //右侧遍历
        while(right!=null){
            right=right.right;
            rightDepth++;
        }
        //第二个终止条件遍历到满二叉树（也就是左右侧深度一样），返回节点数值给上一层
        if(leftDepth==rightDepth){
            return (2<<leftDepth)-1;
            //2的左移,leftDepth从0开始
        }

        //写各层递归
        int leftnum=getNum(root.left);
        int rightnum=getNum(root.right);
        int sum=leftnum+rightnum;
        return sum+1;//加上根节点
    }
}