代码随想录day16【二叉树】二叉树的最大深度 n叉树的最大深度 完全二叉树的节点个数

二叉树的最大深度

力扣题目

1. 理论
   高度& 深度
   求高度：后序遍历
   求深度：前序遍历

   
   

实际：求高度

var maxDepth = function(root) {
    if(!root) return 0
    let leftHeight= maxDepth(root.left)
    let rightHeight= maxDepth(root.right)
    return Math.max(leftHeight,rightHeight)+1
};

n叉树的最大深度

力扣题目链接

var maxDepth = function(root) {
    if(!root) return 0

    let dep=0
    for(let i=0;i<root.children.length;i++){
        dep=Math.max(dep,maxDepth(root.children[i]))
    }
    return dep
};

二叉树的最小深度

leecode题目
审题：最小深度是从根节点到最近叶子节点的最短路径上的节点数量

image.png

思路：

1. 同样利用后序遍历
2. 注意左子结点为空的情况。

var minDepth = function(root) {
    if(!root) return 0
    if(!root.left && root.right) return minDepth(root.right)+1
    if(root.left && !root.right) return minDepth(root.left)+1

    let leftMin = minDepth(root.left)
    let rightMin= minDepth(root.right)
    return Math.min(leftMin,rightMin)+1
};

完全二叉树节点的数量

力扣题目
思路：
法一：普通二叉树遍历（前中后序都可以）
法二：利用完全二叉树的特性:
遇到满二叉树，就返回满二叉树的节点个数。

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算.

image.png

//1.普通二叉树遍历
var countNodes = function(root) {
    if(!root) return 0
    let leftNodes=countNodes(root.left)
    let righNodes=countNodes(root.right)
    return leftNodes+righNodes+1
};

//2. 完全二叉树特性
var countNodes = function(root) {
    if(!root) return 0
    let left =root.left
    let right =root.right
    let leftHeight =0
    let rightHeight=0

    while(left){
        left =left.left
        leftHeight++
    }
    while(right){
        right = right.right
        rightHeight++
    }

    //2<<leftHeight 2左移一位=Math.pow(2,左移位数+1)
    if(leftHeight === rightHeight)return (2<<leftHeight)-1

    let leftNodes = countNodes(root.left)
    let rightNodes=countNodes(root.right)

    return leftNodes+rightNodes+1

};

（迭代法待补充）