二叉樹的最大深度

力扣題目

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題目
審題：最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量

image.png

思路：

1. 同樣利用后序遍歷
2. 注意左子結(jié)點為空的情況。

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

完全二叉樹節(jié)點的數(shù)量

力扣題目
思路：
法一：普通二叉樹遍歷（前中后序都可以）
法二：利用完全二叉樹的特性:
遇到滿二叉樹，就返回滿二叉樹的節(jié)點個數(shù)。

完全二叉樹只有兩種情況，情況一：就是滿二叉樹，情況二：最后一層葉子節(jié)點沒有滿。
對于情況一，可以直接用 2^樹深度 - 1 來計算，注意這里根節(jié)點深度為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,左移位數(shù)+1)
    if(leftHeight === rightHeight)return (2<<leftHeight)-1

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

    return leftNodes+rightNodes+1

};

（迭代法待補充）