题目:Balanced Binary Tree

Minimum Depth of Binary Tree

• Example 1
  Given the following tree [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7

minimum depth = 2

解法1-递归

function minimumDepth(root){
    if(!root) return 0;
    if(!root.left) return 1 + minimumDepth(root.right)
    if(!root.right) return 1 + minimumDepth(root.left)
    return 1+ Math.min(minimumDepth(root.left,root.right))
}

解法2-BST

function minDepth(root){
    if(!root)  return 0;
    let queue = [root]
    let depth = 1; // 为什么取1 不是0,因为下面根节点如果没有左右节点，他还是为1
    while(queue.length){
        let len = queue.length;
        for(let i = 0; i < len; i++){ // 保证每一层遍历完以后，在继续往下遍历判断
            let node = queue.shift()
            if(!node.left && !node.right) return depth
            if(node.left)  queue.push(node.left)
            if(node.right) queue.push(node.right)
        }
        depth++
    }
    return depth
}