代码随想录训练营Day16 | 104.二叉树的最大深度, 111.二叉树的最小深度,222.完全二叉树的节点个数

104. 二叉树的最大深度

迭代法

• 层序遍历，记录总层数，即为二叉树的最大深度

var maxDepth = function(root) {
    if (!root) return 0
    let depth = 0
    let queue = [root]
    while (queue.length) {
        let size = queue.length
        let i = 0
        while (i < size) {
            let cur = queue[0]
            queue.shift()
            i++
            cur.left && queue.push(cur.left)
            cur.right && queue.push(cur.right)
        }
        depth++
    }
    return depth
};

递归法

var maxDepth = function(root) {
    if (!root) return 0
    let maxDep = 0
    const dfs = (root) => {
        if (!root) {
            return 0
        }
        let lDep = dfs(root.left) // 左
        let rDep = dfs(root.right) // 右
        maxDep = Math.max(lDep, rDep) + 1 // 中
        return maxDep
    }
    return dfs(root)
};

111. 二叉树的最小深度

思路

• 最小深度：是从根节点到最近叶子节点的最短路径上的节点数量。
• 与最大深度不同的是：

1. 如果左子树为空，那么最小深度等于右子树深度 + 1
2. 如果右子树为空，那么最小深度等于左子树深度 + 1
3. 如果左右子树都为空，那么最先深度等于 min(左子树深度，右子树深度) + 1

迭代法

var minDepth = function(root) {
    if (!root) return 0
    let minDepth = 0
    let queue = [root]
    while (queue.length){
        let size = queue.length
        let i = 0
        minDepth++
        while(i < size) {
            let cur = queue[0]
            queue.shift()
            if (!cur.left && !cur.right) {
                return minDepth
            }
            cur.left && queue.push(cur.left)
            cur.right && queue.push(cur.right)
            i++
        }
    }
    return minDepth
};

递归法

var minDepth = function(root) {
    if (!root) return 0
    let minDep = 1
    const dfs = (root) => {
        if (!root) {
            return 0
        }
        let lDep = dfs(root.left) // 左
        let rDep = dfs(root.right) // 右
        if (!root.left && root.right) {
           return rDep + 1
        }
        if (root.left && !root.right) {
           return lDep + 1
        }
        minDep = Math.min(lDep, rDep) + 1 // 中
        return minDep
    }
    return dfs(root)
};

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

思路

• 按照普通二叉树求解，层序遍历或者深度遍历，记录节点个数
• 按照完全二叉树求解，将左子树、右子树递归判断是否为满二叉树
• 是满二叉树，根据 2 ^ 树的深度 - 1 求节点个数
• 如何判断是否为满二叉树：递归向左遍历的深度等于递归向右遍历的深度

var countNodes = function(root) {
    if (!root) return 0
    let left = root.left
    let right = root.right
    let leftDepth = 0, rightDepth = 0;
    while (left) {
        left = left.left
        leftDepth++
    }
    while(right) {
        right = right.right;
        rightDepth++;
    }
    if (leftDepth === rightDepth) {
        return Math.pow(2, leftDepth+1) - 1
    }
    return countNodes(root.left) + countNodes(root.right) + 1
};