minimum-depth.js (1504B)
1 //Find the minimum depth to find a leaf and then return the depth. 2 //To solve this I used BFS to search each node on each layer until I found a leaf 3 //when a leaf is found I then return the current depth which is also the minimum depth. 4 //The worst case time complexity of this code is O(n) where n is the number of nodes in the tree 5 //Time: 220ms Beats: 98.72% 6 //Memory: 98.2MB Beats: 5.26% 7 8 /** 9 * Definition for a binary tree node. 10 * function TreeNode(val, left, right) { 11 * this.val = (val===undefined ? 0 : val) 12 * this.left = (left===undefined ? null : left) 13 * this.right = (right===undefined ? null : right) 14 * } 15 */ 16 /** 17 * @param {TreeNode} root 18 * @return {number} 19 */ 20 21 22 var minDepth = function(root) { 23 let node_queue = []; 24 let depth = 0; 25 node_queue.splice(0,0,root); 26 27 if(root == null){ 28 return 0; 29 } 30 if(root.left == null && root.right == null){ 31 return 1; 32 } 33 34 35 while(true){ 36 depth += 1; 37 let start_len = node_queue.length; 38 for(let i = 0 ; i < start_len ; ++i){ 39 let curr_node = node_queue.pop(); 40 if(curr_node.left == null && curr_node.right == null){ 41 return depth; 42 } 43 else{ 44 if(curr_node.left != null){ 45 node_queue.splice(0,0,curr_node.left); 46 } 47 if(curr_node.right != null){ 48 node_queue.splice(0,0,curr_node.right); 49 } 50 } 51 } 52 } 53 54 };