104. 二叉樹(shù)的最大深度

迭代法

• 層序遍歷省撑，記錄總層數(shù)，即為二叉樹(shù)的最大深度

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. 二叉樹(shù)的最小深度

思路

• 最小深度：是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
• 與最大深度不同的是：

1. 如果左子樹(shù)為空，那么最小深度等于右子樹(shù)深度 + 1
2. 如果右子樹(shù)為空，那么最小深度等于左子樹(shù)深度 + 1
3. 如果左右子樹(shù)都為空耐亏，那么最先深度等于 min(左子樹(shù)深度，右子樹(shù)深度) + 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. 完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)

思路

• 按照普通二叉樹(shù)求解沪斟，層序遍歷或者深度遍歷广辰，記錄節(jié)點(diǎn)個(gè)數(shù)
• 按照完全二叉樹(shù)求解，將左子樹(shù)主之、右子樹(shù)遞歸判斷是否為滿二叉樹(shù)
• 是滿二叉樹(shù)择吊，根據(jù) 2 ^ 樹(shù)的深度 - 1 求節(jié)點(diǎn)個(gè)數(shù)
• 如何判斷是否為滿二叉樹(shù)：遞歸向左遍歷的深度等于遞歸向右遍歷的深度

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
};