111二叉树最小深度
寻找到层数最小的叶子节点,即层数最小的左右指针为空的节点
层次迭代法
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int minDepth(TreeNode* root) { TreeNode* node ; //迭代节点 queue<TreeNode*> my_que; //队列 int result = 0; vector<int> min_num; if(root == nullptr) return result; else // 根节点进队列 { my_que.push(root); } while(my_que.empty() != 1) { int size = my_que.size(); result +=1; for(int i=0 ; i<size ; i++) { node = my_que.front(); //该层级的点弹出放入数组 my_que.pop(); // cout<<node->val<<' '<<node->left<<' '<<node->right<<endl; //每一个弹出点的下一个层级左右节点压入队列 if(node->left != nullptr) my_que.push(node->left); if(node->right != nullptr) my_que.push(node->right); //找到叶子节点 if(node->left == nullptr && node->right == nullptr) min_num.push_back(result); } } //排序找到叶子节点所在最小层 sort(min_num.begin(),min_num.end()); return min_num[0]; } };
递归法
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int getdepth(TreeNode* cur) { if(cur == nullptr) return 0; int right_depth , left_depth; //左子树为空,直接测量右子树 if(cur->left == nullptr && cur->right != nullptr) { right_depth = getdepth(cur->right); return 1 + right_depth; }else if(cur->left != nullptr && cur->right == nullptr) //右子树为空,直接测量左子树 { left_depth = getdepth(cur->left); return 1 + left_depth; }else//左右子树都为空或都不为空,左右子树均测量,返回最小值 { left_depth = getdepth(cur->left); right_depth = getdepth(cur->right); return 1 + min(left_depth,right_depth); } } int minDepth(TreeNode* root) { if(root == nullptr) return 0; return getdepth(root); } };
二刷
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int minDepth(TreeNode* root) { if(root == nullptr ) return 0; int left_deep = minDepth(root->left); int right_deep = minDepth(root->right); if(left_deep==0 && right_deep==0) return 0+1 ; else if(left_deep == 0 && right_deep != 0) return right_deep+1; else if(left_deep != 0 && right_deep == 0) return left_deep+1; else return min(left_deep,right_deep)+1; } };