111. Minimum Depth of Binary Tree

成都創(chuàng)新互聯(lián)公司是一家專業(yè)提供孟津企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站制作、成都網(wǎng)站建設(shè)、成都h5網(wǎng)站建設(shè)、小程序制作等業(yè)務(wù)。10年已為孟津眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進(jìn)行中。

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.

思路：

mine思路：

1.采用后序遍歷非遞歸方式，找到葉子節(jié)點(diǎn)，記錄當(dāng)時(shí)棧內(nèi)元素的個(gè)數(shù)到容器中。

2.最后從容器中選擇最小的一個(gè)輸出。

代碼如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        
        int iMinDepth;
        vector<int> depths;
        stack<TreeNode *> s;
        
        TreeNode *p,*q;
        q = NULL;
        p = root;
        if(!root)
            return 0;
        while(p != NULL || s.size() > 0)
        {
            while( p != NULL)
            {
                s.push(p);
                p = p->left;
            }
            if(s.size() > 0)
            {
                p = s.top();
                 
                if( NULL == p->left && NULL == p->right)
                {
                    depths.push_back(s.size());
                }
                 
                if( (NULL == p->right || p->right == q) )
                {
                    q = p;
                    s.pop();
                    p = NULL;
                }
                else
                    p = p->right;
            }
        }
        iMinDepth = depths[0];
        for(int i = 0; i < depths.size(); i++)
        {
            if(depths[i] < iMinDepth)
            {
                iMinDepth = depths[i];
            }
        }
        return iMinDepth;
    }
};

參考其他：http://www.cnblogs.com/bakari/p/4126693.html

有兩種求解的思路，一種采用DFS的思想，一種采用BFS的思想，如下代碼所示：

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

//采用DFS的思想
int maxDepth(TreeNode *root)
{
    if (NULL == root)
        return 0;
    int l = maxDepth(root->left);
    int r = maxDepth(root->right);

    return l > r ? l + 1:r+1;
    //以上這兩種方式有一種更簡(jiǎn)便的方法
    //return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

//采用BFS的方法，引入隊(duì)列
int maxDepth(TreeNode *root)
{
    if (NULL == root)
        return 0;
    queue <TreeNode *> que;
    int nCount = 1;
    int nDepth = 0;// 記錄隊(duì)列里面每一層上的元素

    que.push(root);
    while(!que.empty()) {
        TreeNode *pTemp = que.front();
        que.pop();
        nCount --;

        if (pTemp->left)
            que.push(pTemp->left);
        if (pTemp->right)
            que.push(pTemp->right);
        
        if (nCount == 0) {
            nDepth ++;
            nCount = que.size();
        }
    }
    return nDepth;
}

2016-08-07 10:12:37

網(wǎng)頁名稱：leetCode111.MinimumDepthofBinaryTree二叉樹問題
文章起源：http://www.chinadenli.net/article24/ipphje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、商城網(wǎng)站、定制網(wǎng)站、網(wǎng)站設(shè)計(jì)公司、全網(wǎng)營銷推廣、ChatGPT

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)