Day 16 | 104.二叉树的最大深度、111.二叉树的最小深度、559.N 叉树的最大深度、222.完全二叉树的节点个数

Leetcode 104.二叉树的最大深度

题目：104.二叉树的最大深度 讲解：https://www.bilibili.com/video/BV1Gd4y1V75u

初始思路

昨天用了层序遍历的模板写出了这道题，在每层遍历的时候深度加一即可

代码

// 递归
var maxDepth = function (root) {
    const getDepth = function (node) {
        // 终止条件
        if (!node) return 0
        // 确定单层逻辑
        let leftDepth = getDepth(node.left) // 左
        let rightDepth = getDepth(node.right) // 右
        let depth = 1 + Math.max(leftDepth, rightDepth) // 中
        return depth
    }
    return getDepth(root)
}

var maxDepth = function(root) {
if (!root) return 0
    let queue = []
    queue.push(root)
    // 记录深度
    let depth = 0
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        depth++
        for (let i = 0; i < length; i++){
            // 将这个节点弹出
            let node = queue.shift()
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return depth
};

感想

1. 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
2. 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
3. 使用前序求的就是深度，使用后序求的是高度。而根节点的高度就是二叉树的最大深度

Leetcode 559.N 叉树的最大深度

题目：559.N 叉树的最大深度

初始思路

把遍历左右节点换成children节点

代码

// 递归
var maxDepth = function (root) {
    if (!root) return 0
    let depth = 0
    for (let node of root.children) {
        // 获得所有孩子节点中最大的深度
        depth = Math.max(depth, maxDepth(node))
    }
    // 加上根节点的深度
    return depth + 1
};

// 层序遍历
var maxDepth = function (root) {
    if (!root) return 0
    let queue = []
    queue.push(root)
    let depth = 0
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        depth++
        for (let i = 0; i < length; i++){
            // 将这个节点弹出
            let node = queue.shift()
            // 这里做出改造，遍历children节点
            for (let item of node.children) {
                if (item) queue.push(item)
            }
        }
    }
    return depth
}

感想

1. 可能是层序遍历写多了，感觉比递归更简单是怎么回事。。。

Leetcode 111.二叉树的最小深度

题目：111.二叉树的最小深度

初始思路

这题昨天也用层序遍历的模板写过了。

代码

// 递归
var minDepth = function (root) {
    // 终止条件
    if (!root) return 0
    // 到了叶子节点，返回1
    if (root.left == null && root.right == null) {
        return 1
    }
    // 继续遍历右节点
    if (root.left == null && root.right != null) {
        return 1 + minDepth(root.right)
    }
    if (root.left != null && root.right == null) {
        return 1 + minDepth(root.left)
    }
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1
}

var minDepth = function (root) {
    if (!root) return 0
    let queue = []
    queue.push(root)
    // 记录深度
    let depth = 0
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        depth++
        for (let i = 0; i < length; i++){
            // 将这个节点弹出
            let node = queue.shift()
            if (node.left == null && node.right == null) {
                // 如果左右节点都为空，则该节点深度最小
                return depth
            }
            // 存放当这个节点的左右节点
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return depth
};

感想

1. 注意理解。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。是叶子节点！
2. 如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
3. 反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
4. 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。
5. 

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

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

初始思路

恩。。。获取二叉树深度的时候同时记录节点数量就可以了。

代码

var countNodes = function (root) {
    const getNodesNum = function (node) {
        // 终止条件
        if (!node) return 0
        // 确定单层逻辑
        let leftNum = getNodesNum(node.left) // 左
        let rightNum = getNodesNum(node.right) // 右
        let treeNum = leftNum + rightNum + 1 // 中
        return treeNum
    }
    return getNodesNum(root)
};

var countNodes = function (root) {
    if (!root) return 0
    let queue = []
    queue.push(root)
    // 记录节点数量
    let count = 0
    while (queue.length) {
        // 记录当前层有多少个节点
        let length = queue.length
        for (let i = 0; i < length; i++) {
            // 将这个节点弹出
            let node = queue.shift()
            // 存放当这个节点的左右节点
            count++
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return count
}

// 利用二叉树特性
var countNodes = function (root) {
    if (!root) return 0
    let left = root.left
    let right = root.right
    let leftDepth = 0, rightDepth = 0
    // 求左子树的深度
    while (left) {
        leftDepth++
        left = left.left
    }
    // 求右子树的深度
    while (right) {
        rightDepth++
        right = right.right
    }
    // 如果深度相等，是满二叉树。节点个数是 2^k - 1
    if (leftDepth === rightDepth) {
        return Math.pow(2, leftDepth + 1) - 1
    }
    // 递归寻找左右子树中，肯定有满二叉树的部分
    return countNodes(root.left) + countNodes(root.right) + 1
}

感想

1. 在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
2. 如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止。
   在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。