[LeetCode]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.

【分析】

类似于：LeetCode之Maximum Depth of Binary Tree

【代码】

/*********************************
*   日期：2014-12-30
*   作者：SJF0115
*   题目: 111.Minimum Depth of Binary Tree
*   来源：https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 二叉树节点
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
        // 左子树最小高度
        int leftHeight = minDepth(root->left);
        // 右子树最小高度
        int rightHeight = minDepth(root->right);
        // 只有左子树或者只有右子树或者左右子树都没有
        if(leftHeight == 0 || rightHeight == 0){
            return max(leftHeight,rightHeight) + 1;
        }//if
        // 左右子树都有
        else{
            return min(leftHeight,rightHeight) + 1;
        }
    }
};
// 创建二叉树
TreeNode* CreateTreeByLevel(vector<int> num){
    int len = num.size();
    if(len == 0){
        return NULL;
    }//if
    queue<TreeNode*> queue;
    int index = 0;
    // 创建根节点
    TreeNode *root = new TreeNode(num[index++]);
    // 入队列
    queue.push(root);
    TreeNode *p = NULL;
    while(!queue.empty() && index < len){
        // 出队列
        p = queue.front();
        queue.pop();
        // 左节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *leftNode = new TreeNode(num[index]);
            p->left = leftNode;
            queue.push(leftNode);
        }
        index++;
        // 右节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *rightNode = new TreeNode(num[index]);
            p->right = rightNode;
            queue.push(rightNode);
        }
        index++;
    }//while
    return root;
}

int main() {
    Solution solution;
    // -1代表NULL
    vector<int> num = {4,5,-1,7};
    TreeNode* root = CreateTreeByLevel(num);
    cout<<solution.minDepth(root)<<endl;
}