学步园

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.

思路：先用非递归的方式。定义两个栈S和depth，分别记录节点和从根节点到当前节点的深度，用Min记录最小深度比较即可。

class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == NULL)
        {
            return 0;
        }
        stack<TreeNode*> S;
        stack<int> Depth;
        int val = 0;
        int min = 999999;
        while(root != NULL || !S.empty())
        {
            while(root != NULL)
            {
                S.push(root);
                Depth.push(val + 1);
                val = Depth.top();
                if (root->left == NULL && root->right == NULL)
                {
                    min = (min < Depth.top() ? min : Depth.top());
                }    
                root = root->left;
            }    
            val = Depth.top();
            root = S.top();
            Depth.pop();
            S.pop();
            root = root->right;
        }
        return min;
    }
};

递归方式：当某个节点只有左节点或是右节点时，其深度是该左节点（右节点）的深度+1，这是与求最大深度的区别。

class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == NULL)
        {
            return 0;
        }
        if (root->left == NULL && root->right != NULL)
        {
            return minDepth(root->right) + 1;
        }  
        else if (root->right == NULL && root->left != NULL)  
        {
            return minDepth(root->left) + 1;
        }    
        int left = minDepth(root->left);
        int right = minDepth(root->right);
        return left <= right ? left + 1 : right + 1; 
    }
};