题目: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
}
