leetCode 111. Minimum Depth of Binary Tree 二叉樹問題

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.

思路：

mine思路：

1.采用后序遍歷非遞歸方式，找到葉子節點，記錄當時棧內元素的個數到容器中。

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

代碼如下：

/**
 * 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;
    //以上這兩種方式有一種更簡便的方法
    //return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

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

    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