LeetCode(111)Minimum Depth of Binary Tree

題目如下:

Given a binary tree, find its minimum depth.

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

題目分析：

挺有意思的一道題目，corner cased and edges are the most important parts. 比如，

root為空，

root為唯一的節點

root的左子樹為空或者右子樹為空

我的代碼如下:

// 90ms過大集合
/**
 * 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) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(root!=NULL&&root->left!=NULL&&root->right!=NULL){
            int l=minDepth(root->left);
            int r=minDepth(root->right);
            return (l<r?l:r)+1;
        }else if(root!=NULL&&root->left==NULL){
            return 1+minDepth(root->right);
        }else if(root!=NULL&&root->right==NULL){
            return 1+minDepth(root->left);
        }else{
            return 0;
        }
    }
};
           

總覺得我寫得邏輯上不是特别明白，于是檢視了一下，看到一個更清晰的

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL)
            return 0;
            
        if (root->left == NULL && root->right == NULL)
            return 1;
            
        int leftDepth = minDepth(root->left);
        int rightDepth = minDepth(root->right);
        
        if (leftDepth == 0)
            return rightDepth + 1;
        else if (rightDepth == 0)
            return leftDepth + 1;
        else
            return min(leftDepth, rightDepth) + 1;
    }
};
           

update: 2014-10-06

class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == NULL) return 0;
        else if (root -> left == NULL) return 1 + minDepth(root->right);
        else if (root -> right == NULL) return 1 + minDepth(root->left);
        else {
            TreeNode* left_node = root->left;
            TreeNode* right_node = root->right;
            int left_dep = minDepth(left_node);
            int right_dep = minDepth(right_node);
            return 1 + ((left_dep < right_dep) ? left_dep:right_dep); //注意三目運算符優先級比加号低，是以要用括号括起來。   
        }
    }
};
           

擴充題目:

leetcode 104 Maximum Depth of Binary Tree， 題目在這裡