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

104.二叉树的最大深度

题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
文档讲解：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#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV1Gd4y1V75u

思路

• 之前用层序遍历做过最大深度的题。现在换递归的方法。
• 后序遍历：根节点的高度就是二叉树的最大深度，而高度是从下往上慢慢累加上去的，所以用的是后序遍历（左右中）。
• 前序遍历：代码会比后序遍历复杂一些。从上往下深度依次增加。用了深度回溯，等我学了回溯再回来补起。

代码

class Solution {
    public int maxDepth(TreeNode root) {
        return getMaxHeight(root);
    }

    public int getMaxHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getMaxHeight(root.left);
        int rightHeight = getMaxHeight(root.right);
        int height = 1 + Math.max(leftHeight, rightHeight);
        return height;
    }
	// getMaxHeight()的精简写法，不定义leftHeight和rightHeight，直接写到return里面。
	public int getMaxHeight(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(getMaxHeight(root.left), getMaxHeight(root.right));
    }
}

559.n叉树的最大深度

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

思路

和二叉树不一样的是，需要先遍历每一个孩子的下的深度，每次遍历都和最大深度相比较。

class Solution {
    public int maxDepth(Node root) {
        return getMaxHeight(root);
    }

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

111.二叉树的最小深度

题目链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/
文档讲解：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#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV1QD4y1B7e2

思路

• 这道题同样也可以用层序遍历解出。下面是递归法。
• 也是用后序遍历来解决。但在求出左右子树的深度之后，不能直接比较选最小值。因为如果根节点左子树为空，右子树深度为2，那这样算出来根节点最小深度就是1 + 0了。在这部分要分情况来选择。

代码

class Solution {
    public int minDepth(TreeNode root) {
        return getMaxHeight(root);
    }

    public int getMaxHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getMaxHeight(root.left);
        int rightHeight = getMaxHeight(root.right);
        // 当左子树为空，就选择右子树的高度。
        if (root.left == null && root.right != null) return 1 + rightHeight;
        // 当右子树为空，就选择左子树的高度。
        else if (root.left != null && root.right == null) return 1 + leftHeight;
        // 如果两边都不为空，就选最小高度。
        return 1 + Math.min(leftHeight, rightHeight);
    }
}

222.完全二叉树的节点个数

题目链接：https://leetcode.cn/problems/count-complete-tree-nodes/
文档讲解：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#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解：https://www.bilibili.com/video/BV1eW4y1B7pD

思路

• 如完全二叉树的特点是，除了底层节点，上面的结点都是满的，而底层节点从左到右一次排开，中间不能有剩余。所以虽然这道题可以用二叉树的各种遍历方法解决，但是最好是使用完全二叉树的特性进行解决。
• 通过遍历左侧和右侧的深度，来判断该子树是否为满二叉树，如果是满二叉树，节点个数就是2ⁿ - 1 个。

代码

class Solution {
    public int countNodes(TreeNode root) {
        return getCount(root);
    }

    public int getCount(TreeNode root) {
        if (root == null) return 0;
        // 满二叉树也是一个终止条件
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftCount = 0, rightCount = 0;
        while (left != null) {
            leftCount++;
            left = left.left;
        }
        while (right != null) {
            rightCount++;
            right = right.right;
        }
        if (leftCount == rightCount) return (2 << leftCount) - 1; 

        return 1 + getCount(root.left) + getCount(root.right);
    }
}