leetcode 111 二叉树的最小深度

leetcode 111 二叉树的最小深度

 

 

 1 /*
 2  * @lc app=leetcode.cn id=111 lang=cpp
 3  *
 4  * [111] 二叉树的最小深度
 5  */
 6 
 7 // @lc code=start
 8 /**
 9  * Definition for a binary tree node.
10  * struct TreeNode {
11  *     int val;
12  *     TreeNode *left;
13  *     TreeNode *right;
14  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
15  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
16  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
17  * };
18  */
19 class Solution {
20 public:
21     /*
22     终止条件、返回值和递归过程:
23 1)当前节点root为空时,说明此处树的高度为0,0也是最小值。
24 2)当前节点root的左子树和右子树都为空时,说明此处树的高度为1,1也是最小值。
25 3)如果为其他情况,则说明当前节点有值,且需要分别计算其左右子树的最小深度,返回最小深度+1,+1表示当前节点存在有1个深度。
26 时间复杂度:O(n),n为树的节点数量。
27     */
28     int minDepth(TreeNode* root) {
29          //当前节点root为空时,说明此处树的高度为0,0也是最小值
30         if(!root) return 0;
31         //当到达叶子节点时,叶子节点的深度为1
32        if(root->left==nullptr&&root->right==nullptr) return 1;
33        int m=INT_MAX;
34        //如果为其他情况,则说明当前节点有值,且需要分别计算其左右子树的最小深度,返回最小深度+1,+1表示当前节点存在有1个深度
35        if(root->left!=nullptr) m=min(minDepth(root->left),m);
36        if(root->right!=nullptr) m=min(minDepth(root->right),m);
37        return m+1;
38     }
39 };
40 // @lc code=end

 

上一篇:C#回调函数的简单讲解与应用例子,简单例子明白意义所在


下一篇:动态区间异或和