代码随想录算法训练营第16天 |（二叉树3 104.二叉树的最大深度 559. N叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

104.二叉树的最大深度 （优先掌握递归）（昨天用层序迭代做过

什么是深度，什么是高度，如何求深度，如何求高度，这里有关系到二叉树的遍历方式。
大家 要先看视频讲解，就知道以上我说的内容了，很多录友刷过这道题，但理解的还不够。
题目链接：104.二叉树的最大深度
文章讲解/视频讲解：104.二叉树的最大深度

解题思路

求高度：后序遍历 根节点的高度就是这棵二叉树的最大深度
求深度：前序遍历
递归三部曲：

1. 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
2. 确定终止条件：如果为空节点的话，就返回0，表示高度为0。
3. 确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

 // 递归  优先掌握
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

 // 层序遍历 迭代
class Solution {
    public int maxDepth(TreeNode root) {
        int res = 0;
        Deque<TreeNode> que = new LinkedList<>(); //辅助队列
        if (root == null) {
            return res;
        }

        que.offer(root);  // 根节点入队
        while (!que.isEmpty()) {
            
            int len = que.size();

            for(int i = 0; i < len; i++) {
                TreeNode peek = que.poll(); //当前层元素依次出队
                
                // 下一层元素入队
                if (peek.left != null) que.offer(peek.left);
                if (peek.right != null) que.offer(peek.right);
            }
            res++;            
        }
        return res;
    }
}

559. N叉树的最大深度

题目链接：559. N叉树的最大深度

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

// 层序迭代
class Solution {
    public int maxDepth(Node root) {
        if(root == null) return 0;
        int ans = 0;
        Deque<Node> d = new ArrayDeque<>();
        d.addLast(root);
        while(!d.isEmpty()){
            int size = d.size();
            while(size-- > 0){
                Node t = d.pollFirst();
                for(Node node : t.children){
                    d.addLast(node);
                }
            }
            ans++;
        }
        return ans;
    }
}

111.二叉树的最小深度 （优先掌握递归）（昨天用层序迭代做过

先看视频讲解，和最大深度 看似差不多，其实 差距还挺大，有坑。
题目链接：111.二叉树的最小深度
文章讲解/视频讲解：111.二叉树的最小深度

解题思路

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。，注意是叶子节点。什么是叶子节点，左右孩子都为空的节点才是叶子节点！ 求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
递归三部曲：

1. 确定递归函数的参数和返回值
2. 确定终止条件
3. 确定单层遍历的逻辑（和上道题求最大深度有很大不同，我们要明确何为叶子节点

 //递归  后序遍历
class Solution {
    public int minDepth(TreeNode root){
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        // 当一个左子树为空，右不为空，这时并不是最低点
        if(root.left == null && root.right != null){
            return rightDepth + 1;
        }
        // 当一个右子树为空，左不为空，这时并不是最低点
        if(root.left != null && root.right == null){
            return leftDepth + 1;
        }
        return Math.min(leftDepth, rightDepth) + 1;        
    }
}

// 层序 迭代
class Solution {
    public int minDepth(TreeNode root){
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            depth++;
            TreeNode cur = null;
            for (int i = 0; i < size; i++) {
                cur = queue.poll();
                //如果当前节点的左右孩子都为空，直接返回最小深度
                if (cur.left == null && cur.right == null){
                    return depth;
                }
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
        }
        return depth;
    }
}

222.完全二叉树的节点个数（优先掌握递归）（需复习

需要了解，普通二叉树 怎么求，完全二叉树又怎么求
题目链接：222.完全二叉树的节点个数
文章讲解/视频讲解：222.完全二叉树的节点个数

解题思路（要了解完全二叉树的特性，基于此特性求解才有意义

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。

// 递归 后序遍历  利用二叉树的性质  这种要掌握
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0;
        while(left != null){  // 求左子树深度
            left = left.left;
            leftDepth++;
        }
        while(right != null){ // 求右子树深度
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

// 按普通二叉树进行递归
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) {
        Deque<TreeNode> que = new LinkedList<>(); //辅助队列
        int num = 0;
        if (root == null) {
            return num;
        }
        que.offer(root);  // 根节点入队
        while (!que.isEmpty()) {
            int len = que.size();
            for(int i = 0; i < len; i++) {
                TreeNode peek = que.poll(); //当前层元素依次出队
                num++;
                // 下一层元素入队
                if (peek.left != null) que.offer(peek.left);
                if (peek.right != null) que.offer(peek.right);
            }
        }
        return num;
    }
}