程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Minimum Depth of Binary Tree

leetcode筆記:Minimum Depth of Binary Tree

編輯:關於C++

一. 題目描述

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;  
    }  
};

四. 小結

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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved