代码随想录算法训练营第十四天-104二叉树的最大深度、111二叉树的最小深度、222完全二叉树的节点个数

前言
状态：104、111 可以 AC，222 没有思路
更新

1	24.06.04 初始记录

初步题解

104 二叉树的最大深度

题目链接：(https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/)

/**  
 * 思路：递归计算左右子树的深度。取较大值  
 * @param root 根节点  
 * @return 结果  
 */  
public int maxDepth(TreeNode root) {  
    if (root == null) {  
        return 0;  
    }  
    int leftLength = maxDepth(root.left);  
    int rightLength = maxDepth(root.right);  
    return 1 + Math.max(leftLength, rightLength);  
}

111 二叉树的最小深度

题目链接：(https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/)

/**  
 * 思路：  
 * 递归终止条件  
 * 1.根节点为空，直接返回0  
 * 2.根节点的左右节点有一个为空，返回另一个节点的最小深度  
 *  
 * @param root 根节点  
 * @return 结果  
 */  
public int minDepth(TreeNode root) {  
    if (root == null) {  
        return 0;  
    }  
  
    if (root.right == null) {  
        return 1 + minDepth(root.left);  
    }  
    if (root.left == null) {  
        return 1 + minDepth(root.right);  
    }  
  
    return 1 + Math.min(minDepth(root.right), minDepth(root.left));  
}

222 完全二叉树的节点个数

题目链接:(https://leetcode.cn/problems/count-complete-tree-nodes/description/)

没有 AC，思路只有一半。根据题解：递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后按满二叉树的情况来算。

// 错误解法，正确解法在看解析部分。
/**  
 * 思路：既然是完全二叉树。深度可以很简单的求出来  
 * @param root 根节点  
 * @return 结果  
 */  
public int countNodes(TreeNode root) {  
    int depth = getDepth(root);  
    // n - 1 层的节点数量  
    int num = (depth - 1) ^ 2 - 1;  
}  
  
  
/**  
 * 求完全二叉树的深度  
 * @param root 根节点  
 * @return 结果  
 */  
private int getDepth(TreeNode root) {  
    int depth = 0;  
    while (root != null) {  
        depth++;  
        root = root.left;  
    }  
    return depth;  
}

看解析

104 二叉树的最大深度

题目链接/文章讲解/视频讲解：(https://programmercarl.com/0104.二叉树的最大深度.html)

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从 0 开始还是从 1 开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从 0 开始还是从 1 开始）
根节点的高度就是二叉树的最大深度。

559. N 叉树的最大深度

题目链接 (https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/)

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

111 二叉树的最小深度

题目链接/文章讲解/视频讲解：(https://programmercarl.com/0111.二叉树的最小深度.html)

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 注意是叶子节点。（左右孩子都为空的节点才是叶子节点）

222 完全二叉树的节点个数

题目链接/文章讲解/视频讲解：(https://programmercarl.com/0222.完全二叉树的节点个数.html)

递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后按满二叉树的情况来算。所以需要判断是否是满二叉树

/**  
 * 完全二叉树求节点  
 * @param root 根节点  
 * @return 结果  
 */  
public int countNodes(TreeNode root) {  
    if (root == null) {  
        return 0;  
    }  
  
    TreeNode left = root.left;  
    TreeNode right = root.right;  
  
    int leftLength = 0, rightLength = 0;  
    while (left != null) {  
        left = left.left;  
        leftLength++;  
    }  
    while (right != null) {  
        right = right.right;  
        rightLength++;  
    }  
    if (leftLength == rightLength) {  
        return (2 << leftLength) - 1;  
    }  
    return countNodes(root.left) + countNodes(root.right) + 1;  
}