更新时间:2022-08-12 18:56:59
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; }