代码随想录-算法训练营day16【二叉树03：二叉树的最大深度、二叉树的最小深度、完全二叉树的节点个数】

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

第六章  二叉树part03

今日内容： 

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

迭代法，大家可以直接过，二刷有精力的时候 再去掌握迭代法。

 详细布置 

 104.二叉树的最大深度 （优先掌握递归）

什么是深度，什么是高度，如何求深度，如何求高度，这里有关系到二叉树的遍历方式。

大家 要先看视频讲解，就知道以上我说的内容了，很多录友刷过这道题，但理解的还不够。

题目链接/文章讲解/视频讲解： https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html  

 111.二叉树的最小深度 （优先掌握递归）

先看视频讲解，和最大深度 看似差不多，其实 差距还挺大，有坑。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html 


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

需要了解，普通二叉树 怎么求，完全二叉树又怎么求

题目链接/文章讲解/视频讲解：https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html  

往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv

目录

0104_二叉树的最大深度

0559_n叉树的最大深度

0111_二叉树的最小深度

0222_完全二叉树的节点个数

0104_二叉树的最大深度

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;

import java.util.Deque;
import java.util.LinkedList;

public class _0104_二叉树的最大深度 {
}

/**
 * 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 Solution0104 {
    public int maxDepth(TreeNode root) {
        int depth = 0;
        if (root == null) {
            return depth;
        }
        Deque<TreeNode> deque = new LinkedList<TreeNode>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
            depth++;
        }
        return depth;
    }

    public int maxDepth2(TreeNode root) {
//        if (root == null) return 0;
//        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        int depth = 0;
        if (root == null) {
            return depth;
        }
        int left = maxDepth2(root.left);
        int right = maxDepth2(root.right);
        depth = 1 + Math.max(left, right);
        return depth;
    }
}

class Solution0104_2 {
    /**
     * 递归法
     */
    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;
    }

    /**
     * 迭代法，使用层序遍历
     */
    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
        }
        return depth;
    }
}

class Solution0104_3 {
    /**
     * 递归法(求深度法)
     */
    int maxnum = 0;//定义最大深度

    public int maxDepth(TreeNode root) {
        ans(root, 0);
        return maxnum;
    }

    //递归求解最大深度
    void ans(TreeNode tr, int tmp) {
        if (tr == null) return;
        tmp++;
        maxnum = maxnum < tmp ? tmp : maxnum;
        ans(tr.left, tmp);
        ans(tr.right, tmp);
        tmp--;
    }
}

0559_n叉树的最大深度

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class _0559_N叉树的最大深度 {
}

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution0559 {
    public int maxDepth(Node2 root) {
        if (root == null) {
            return 0;
        }
        Deque<Node2> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                Node2 poll = deque.poll();
                if (poll.children != null) {
                    for (Node2 x : poll.children) {
                        deque.offer(x);
                    }
                }
            }
            depth++;
        }
        return depth;
    }
}

class Solution0559_2 {
    public int maxDepth(Node2 root) {
        return getDepth(root);
    }

    public int getDepth(Node2 node) {
        int depth = 0;
        if (node == null) {
            return depth;
        }
        for (Node2 x : node.children) {
            int temp = getDepth(x);
            if (depth < temp) {
                depth = temp;
            }
        }
        return depth + 1;
    }
}

class Solution0559_3 {
    /*递归法，后序遍历求root节点的高度*/
    public int maxDepth(Node2 root) {
        if (root == null) return 0;
        int depth = 0;
        if (root.children != null) {
            for (Node2 child : root.children) {
                depth = Math.max(depth, maxDepth(child));
            }
        }
        return depth + 1; //中节点
    }

    /**
     * 迭代法，使用层序遍历
     */
    public int maxDepth2(Node2 root) {
        if (root == null) return 0;
        int depth = 0;
        Queue<Node2> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            depth++;
            int len = que.size();
            while (len > 0) {
                Node2 node = que.poll();
                for (int i = 0; i < node.children.size(); i++)
                    if (node.children.get(i) != null)
                        que.offer(node.children.get(i));
                len--;
            }
        }
        return depth;
    }
}

0111_二叉树的最小深度

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;

import java.util.Deque;
import java.util.LinkedList;

public class _0111_二叉树的最小深度 {
}

/**
 * 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 Solution0111 {
    /**
     * 递归法，相比求MaxDepth要复杂点
     * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null) {
            return rightDepth + 1;
        }
        if (root.right == null) {
            return leftDepth + 1;
        }
        // 左右结点都不为null
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

class Solution0111_2 {
    /**
     * 递归法（思路来自二叉树最大深度的递归法）
     * 该题求最小深度，最小深度为根节点到叶子节点的深度，所以在迭代到每个叶子节点时更新最小值。
     */
    int depth = 0;

    int minDepth = Integer.MAX_VALUE;//定义最小深度，初始化最大值

    public int minDepth(TreeNode root) {
        dep(root);
        return minDepth == Integer.MAX_VALUE ? 0 : minDepth;
    }

    void dep(TreeNode root) {
        if (root == null) return;
        //递归开始，深度增加
        depth++;
        dep(root.left);
        dep(root.right);
        //该位置表示递归到叶子节点了，需要更新最小深度minDepth
        if (root.left == null && root.right == null)
            minDepth = Math.min(minDepth, depth);
        //递归结束，深度减小
        depth--;
    }
}

class Solution0111_3 {
    /**
     * 迭代法，层序遍历
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                if (poll.left == null && poll.right == null) {
                    //是叶子结点，直接返回depth，因为从上往下遍历，所以该值就是最小值
                    return depth;
                }
                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
        }
        return depth;
    }
}

0222_完全二叉树的节点个数

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class _0222_完全二叉树的节点个数 {
}

class Solution0222 {
    public int countNodes(TreeNode root) {//通用递归解法
        if (root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

    public int countNodes2(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) {
                TreeNode cur = queue.poll();
                result++;
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
        }
        return result;
    }

    public int countNodes3(TreeNode root) {//二叉树层序遍历模板
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int num = 1;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                if (poll.left != null) {
                    deque.offer(poll.left);
                    num++;
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                    num++;
                }
            }
        }
        return num;
    }

    /**
     * 针对完全二叉树的解法
     * 满二叉树的结点数为：2^depth - 1
     */
    public int countNodes4(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0; //这里初始为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;
    }
}