leetcode筆記：Minimum Depth of Binary Tree

leetcode筆記：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.

二. 題目分析

這道題屬於二叉樹的深度優先搜索，然後返回深度最小的值，可以遞歸（當然，也可以使用迭代）來實現。遞歸退出的條件是到達葉子節點或者到達空子樹，使用空子樹作為退出條件比較容易進行判斷，只要該結點的指針值為NULL時，就可以判斷空子樹的深度為0。因此，可以將每個結點的左右兩個子樹的深度返回給父節點，父節點選擇比較小的深度，然後再返回給祖先結點，以此類推，最後返回給根結點，得到最終結果。

這種方法的時間復雜度為：O(n)，空間復雜度為：O(logn)。

三. 示例代碼

struct TreeNode  
{  
    int val;  
    TreeNode *left;  
    TreeNode *right;  
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
};  


class Solution  
{  
public:  
    int minDepth(TreeNode* root)  
    {  
        if (!root)  
            return 0;  

        int Result = 1;  
        int Left = minDepth(root->left);  
        int Right = minDepth(root->right);  

        if (Left * Right)  
            Result += Left > Right? Right : Left;  
        else  
            result += Right + Left;  
        return Result;  
    }  
};

四. 小結

這是一道對二叉樹進行遞歸來得到結果的題，遞歸在二叉樹的相關題目中還是考察得比較多的。