力扣刷题记录-二叉树深度问题

力扣 104. 二叉树的最大深度

求一棵二叉树的最大的深度，有递归和迭代法。

//递归法
class Solution {
    public int maxDepth(TreeNode root) {
        //若当前结点为空，则为叶子结点，高度为0；
        if(root==null)return 0;
        //当前结点最大深度为左右子树最大深度+1（+1是因为要算上当前结点的高度1）
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

/*
层序遍历比较适合求深度，因为层序遍历是一层层遍历下去，只要在每层里面给depth+1就行，层序遍历模板用得较为熟练，用起来比较方便。
*/
//迭代法（层序遍历模板）
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)return 0;
        Queue<TreeNode> que=new LinkedList<>();
        int depth=0;//记录当前遍历的深度
        que.offer(root);
        while(!que.isEmpty()){
            int len=que.size();
            depth++;//外层while遍历所有层
            while(len-->0){//内层while循环用来遍历这一层的所有结点
                TreeNode cur=que.poll();
                if(cur.left!=null)que.offer(cur.left);
                if(cur.right!=null)que.offer(cur.right);
            }
        }
        return depth;
    }
}

力扣 559. N 叉树的最大深度

像上题一样，可以用递归和迭代方法。

递归法中需要注意，不同于二叉树的求最大深度，n叉树有多个孩子结点，需要在访问当前结点的时候，遍历孩子结点，并求出下一层子结点中的最大深度，这需要使用depth记录下一层的子结点的最大深度；在最后返回值+1，也就是还需要算上当前遍历到的结点的1的高度。

//递归法
class Solution {
    public int maxDepth(Node root) {
        if(root==null)return 0;
        int depth=0;
        for(Node child:root.children){
            depth=Math.max(maxDepth(child),depth);
        }
        return depth+1;
    }
}

//迭代法（层次遍历模板）
class Solution {
    public int maxDepth(Node root) {
        if(root==null)return 0;
        Queue<Node>que=new LinkedList<>();
        que.offer(root);
        int depth=0;
        while(!que.isEmpty()){
            int len=que.size();
            depth++;
            while(len-->0){
                Node cur=que.poll();
                for(Node child:cur.children)//多了遍历所有孩子的步骤
                    if(child!=null)que.offer(child);   
            }
        }
        return depth;
    }
}

力扣 111. 二叉树的最小深度

求最小深度需要注意，最小深度是从根节点到最近叶子节点的最短路径上的节点数量，如图：（为方便说明，采用代码随想录公众号的图片）
·因此，在递归的方法里，需要考虑左右子树分别为空的情况，排除这两种情况之后，还剩下左右子树都为空，和左右子树都存在的情况，则返回1+左右子树最小深度（若均非空，则可递归计算，若均为空，则相当于1+0）。这样的式子相当于省略了：

if(root.left==null&&root.right==null)return 1;

这一句的判断。

·在迭代方法里，由于是层序遍历从上往下的遍历，因此碰到的第一个叶子结点（左右子树都为空的结点）所在的那层深度就是最小深度。

递归和迭代的代码如下：

//递归法
class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)return 0;
        //左子树空，右子树不空，最小深度为根节点到右子树的叶子结点的深度
        if(root.left==null&&root.right!=null)return 1+minDepth(root.right);
        //右子树空，左子树不空，最小深度为根节点到左子树的叶子结点的深度
        if(root.left!=null&&root.right==null)return 1+minDepth(root.left);
        //排除了左右子树分别为空的情况，还剩下左右子树都为空，和左右子树都存在的情况，这两种情况都可以用这个式子计算：当前遍历到的结点的最小深度为1+左/右子树最小的深度
        return 1+Math.min(minDepth(root.left),minDepth(root.right));
    }
}


//迭代法（层序遍历模板）
class Solution {
    public int minDepth(TreeNode root) {
        if(root==null)return 0;
        int depth=0;
        Queue<TreeNode> que=new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int len=que.size();
            depth++;
            while(len-->0){
                TreeNode cur=que.poll();
                if(cur.left!=null)que.offer(cur.left);
                if(cur.right!=null)que.offer(cur.right);
                //如果当前结点无左右孩子，说明它是叶子结点，则此层有最小深度
                if(cur.left==null&&cur.right==null)return depth;
            }
        }
        return depth;//如果不会提前返回，说明会一直到最后一层
    }
}