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

104.二叉树最大深度

扣除主题链接(opens new window)

给定一棵二叉树，找出它的最大深度。

二叉树的深度是从根节点到最远叶节点最长路径的节点数。

说明: 叶节点是指无子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

回到它最大的深度 3 。

思想：

递归法，第一步，返回值为int类型，输入元素为节点；第二步，终止条件是，通过根节点返回；第三步，中间逻辑是通过节点的序列或中间序列。

class Solution {    public int maxDepth(TreeNode root) {        return getDepth(root);    }    private int getDepth(TreeNode cur){        if(cur == null) return 0;        int left = getDepth(cur.left);        int right = getDepth(cur.right);        return 1+Math.max(left,right);    }}

559.N叉树的最大深度

扣除主题链接(opens new window)

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

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

例如，给定一个 3叉树 :

我们应该回到它的最大深度，3。

思路：

与二叉树一致，只需考虑N叉树的遍历写法

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

111.二叉树最小深度

扣除主题链接(opens new window)

给定一棵二叉树，找出它的最小深度。

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

说明:叶节点是指无子节点的节点。

示例:

给定二叉树[3，9，20，null,null,15,7],

回到它的最小深度 2。

思路：

要判断最小深度，需要注意的是，必须是叶节点，才能算是深度计算

class Solution {    public int minDepth(TreeNode root) {        return getDepth(root);    }    private int getDepth(TreeNode cur){        if(cur == null) return 0;        int leftDepth = getDepth(cur.left);        int rightDepth = getDepth(cur.right);        if(cur.left == null && cur.right != null){            return 1+rightDepth;        }        if(cur.left != null && cur.right == null){            return 1+leftDepth;        }        return 1 + Math.min(leftDepth, rightDepth);    }}

222.完全二叉树的节点数

扣除主题链接(opens new window)

给出一棵完整的二叉树，找出树的节点数。

示例 1：

• 输入：root = [1，2，3，4，5]
• 输出：6

示例 2：

• 输入：root = []
• 输出：0

示例 3：

• 输入：root = [1]
• 输出：1

提示：

• 树中节点的数量范围为[0， 5 * 10^4]
• 0 <= Node.val <= 5 * 10^4
• 标题数据保证输入的树是 完全二叉树

思路：

递归的想法是，前序遍历，遇空返回0，分别计算左右子树的节点数。

class Solution {    public int countNodes(TreeNode root) {        return count(root);    }    private int count(TreeNode cur){        if(cur == null) return 0;        int leftDe = count(cur.left);        int rightDe = count(cur.right);        return 1+leftDe+rightDe;     }}