Minimum Depth of Binary Tree

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

cpp code : 暴力求解，递归到每一个叶子节点，记录深度，然后维护一个最小的值即可。此算法效率不高，若存在一个叶子节点很矮，而其他叶子节点很深的情况，需要遍历到所有深的结点。

 

 

/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
    int minDepth(TreeNode *root) {  
        // Note: The Solution object is instantiated only once and is reused by each test case.  
        if(root == NULL)  
            return 0;  
        int depth = INT_MAX;  
        int tmp = 1;  
        recursion(root, tmp, depth);  
        return depth;  
    }  
    void recursion(TreeNode *root, int tmp, int &depth)  
    {  
        if(root->left == NULL && root->right == NULL)  
        {  
            if(tmp < depth)  
                depth = tmp;  
            return ;  
        }  
        if(root->left)  
        {  
            recursion(root->left, tmp + 1, depth);  
        }  
        if(root->right)  
        {  
            recursion(root->right, tmp + 1, depth);  
        }  
    }  
};  

 

 

比较高效的做法是：使用层序遍历二叉树，遇到叶子节点即返回深度。

java code :

 

/** 
 * Definition for binary tree 
 * public class TreeNode { 
 *     int val; 
 *     TreeNode left; 
 *     TreeNode right; 
 *     TreeNode(int x) { val = x; } 
 * } 
 */  
public class Solution {  
    public int minDepth(TreeNode root) {  
        // Note: The Solution object is instantiated only once and is reused by each test case.  
        if(root == null)  
            return 0;  
        Queue<TreeNode> que = new LinkedList<TreeNode>();  
        que.add(root);  
        que.add(null);  
        int level = 1;  
        while(true)  
        {  
            TreeNode cur = que.poll();  
            if(que.isEmpty())  
                break;  
            if(cur == null)  
            {  
                que.add(null);  
                level++;  
                continue;  
            }  
            if(cur.left == null && cur.right == null)  
            {  
                return level;  
            }  
            if(cur.left != null)  
                que.add(cur.left);  
            if(cur.right != null)  
                que.add(cur.right);  
        }  
        return level;  
          
    }  
      
}  

 

 

补充：软件开发 , C++ ,