Minimum Depth of Binary Tree Solutions in C++

// Source : https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
// Author : Hao Chen
// Date   : 2014-06-22



/**
 * Definition for binary tree
 * 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==NULL){
            return 0;
        }
        if (root->left==NULL && root->right==NULL){
            return 1;
        }
        int left=INT_MAX;
        if (root->left){
            left = minDepth(root->left) + 1 ;
        }
        int right=INT_MAX;
        if (root->right){
            right = minDepth(root->right) + 1;
        }
        
        return left<right ? left : right;
        
    }
};

#include <algorithm>

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;
        else if (!root->left and !root->right) return 1;
        else if (root->left and root->right) return 1 + std::min(minDepth(root->left), minDepth(root->right));
        else return 1 + (root->left ? minDepth(root->left) : minDepth(root->right));
    }
};

/// Source : https://leetcode.com/problems/minimum-depth-of-binary-tree/
/// Author : liuyubobobo
/// Time   : 2018-06-02

#include <iostream>

using namespace std;


/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/// Recursive
/// Time Complexity: O(n)
/// Space Complexity: O(h)
class Solution {
public:
    int minDepth(TreeNode* root) {

        if(root == NULL)
            return 0;

        if(root->left == NULL && root->right == NULL)
            return 1;

        int ret = INT_MAX;
        if(root->left != NULL)
            ret = min(ret, 1 + minDepth(root->left));
        if(root->right != NULL)
            ret = min(ret, 1 + minDepth(root->right));
        return ret;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-depth-of-binary-tree/
/// Author : liuyubobobo
/// Time   : 2018-10-29

#include <iostream>
#include <stack>

using namespace std;


/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/// Non-Recursive
/// Using stack
///
/// Time Complexity: O(n)
/// Space Complexity: O(h)
class Solution {
public:
    int minDepth(TreeNode* root) {

        if(root == NULL)
            return 0;

        stack<pair<TreeNode*, int>> stack;
        stack.push(make_pair(root, 1));
        int res = INT_MAX;
        while(!stack.empty()){
            TreeNode* cur = stack.top().first;
            int step = stack.top().second;
            stack.pop();

            if(!cur->left && !cur->right)
                res = min(res, step);
            else{
                if(cur->left)
                    stack.push(make_pair(cur->left, step + 1));
                if(cur->right)
                    stack.push(make_pair(cur->right, step + 1));
            }
        }
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-depth-of-binary-tree/
/// Author : liuyubobobo
/// Time   : 2018-10-29

#include <iostream>
#include <queue>
#include <cassert>

using namespace std;


/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/// Non-Recursive
/// Using BFS may not visit all the nodes :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(h)
class Solution {
public:
    int minDepth(TreeNode* root) {

        if(root == NULL)
            return 0;

        queue<pair<TreeNode*, int>> queue;
        queue.push(make_pair(root, 1));
        while(!queue.empty()){
            TreeNode* cur = queue.front().first;
            int step = queue.front().second;
            queue.pop();

            if(!cur->left && !cur->right)
                return step;
            else{
                if(cur->left)
                    queue.push(make_pair(cur->left, step + 1));
                if(cur->right)
                    queue.push(make_pair(cur->right, step + 1));
            }
        }

        assert(false);
        return -1;
    }
};


int main() {

    return 0;
}