代码随想录刷题学习日记

仅为个人记录复盘学习历程，解题思路来自代码随想录

代码随想录刷题笔记总结网址:
代码随想录

559.n叉树的最大深度（层序遍历法）

给定一个 n 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

提供参数：根结点root

关键思路：和二叉树的层序遍历找最大深度一样，不再赘述。

代码大致如下：

    public int maxDepth(Node root) {
        //
        int dep=0;
        Queue<Node>queue=new LinkedList<>();
        if(root==null)return dep;
        queue.offer(root);
        while(!queue.isEmpty()){
            int len=queue.size();
            dep++;
            for(int i=0;i<len;i++){
                Node node=queue.poll();
                for(Node child:node.children){
                    if(child!=null)queue.offer(child);
                }
            }

        }
        return dep;
        
    }

111.二叉树的最小深度（递归法）

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

二叉树的深度：从根结点到该结点路径上的节点数

二叉树的高度：指从该节点到叶子节点的最长简单路径上的节点数

提供参数：根结点root

主要操作：

递归三要素

1.参数和返回值类型：

返回深度int型，参数为根结点root

2.判断终止条件：

如果访问到空节点，返回深度为0

3.单次递归逻辑：

获取左子树深度；

获取右子树深度；

排除左右一棵子树为空，一颗不为空的情况：

左边为空，返回右子树深度+1

右边为空，返回左子树深度+1

返回左右子树深度的较小值+1

代码大致如下：

public int minDepth(TreeNode root) {
        //递归
        //终止条件
        if(root==null)return 0;
        //单层逻辑，后续遍历
        int left=minDepth(root.left);
        int right=minDepth(root.right);

        //左子树为空，右子树不为空
        if(root.left==null&&root.right!=null)return 1+right;
        if(root.right==null&&root.left!=null)return 1+left;

        //右子树为空，左子树不为空

        int res=Math.min(left,right);
        return 1+res;
    }