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

LeetCode 104 二叉树的最大深度

本题思想：用后序遍历的思想，先判断出左子树的深度，然后在右子树的深度。最后取大的那一个再加上根节点。就是最大深度。

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

---

LeetCode 559 N叉树的最大深度

class Solution {
    public int maxDepth(Node root) {
        if(root == null){
            return 0;
        }
        int res = 0;
        // 遍历每个节点，获得最大深度
        for(Node children : root.children){
            res = Math.max(maxDepth(children),res);
        }
        // 最后加上根节点
        return res+1;
    }
}

---

LeetCode 111 二叉树的最小深度

本题思路: 和求最大深度，一个思想。不过有一坑

注意：左子树为空的情况，或者是 右子树为空的情况！
要分别判断！

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        // 进行左右子树判断
        if(root.left == null && root.right != null){
            return 1 + right;
        }else if(root.left != null && root.right == null){
            return 1 + left;
        }
        int res = Math.min(left,right);
        return res+1;
    }
}

---

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

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