建站最便宜的平台,国家建设部网站证书查询,航达建设网站,企业网站模板哪个好文章目录 一、题目二、层序遍历法三、递归法四、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、层序遍历法 思路分析#xff1a;两道题都可以用层序遍历#xff08;迭代法#xff09;来做#xff0c;遍历完… 文章目录 一、题目二、层序遍历法三、递归法四、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、层序遍历法 思路分析两道题都可以用层序遍历迭代法来做遍历完一层深度变量depth就。找最小深度实际上等价于找离根节点最近的叶子节点我们在遍历每一个节点时判断它的左右节点是否为空若为空则为叶子节点输出此时的depth。 找最大深度程序如下
class Solution {
public:// 找最大深度int maxDepth(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);int Depth 0, size 0; // 根节点深度定义为1while (!que.empty()) {Depth;size que.size(); // size必须固定, que.size()是不断变化的for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (node-left) que.push(node-left);if (node-right) que.push(node-right);} }return Depth;}
};找最小深度程序如下
class Solution2 {
public:// 找最小深度int minDepth(TreeNode* root) {if (!root) return 0;queueTreeNode* que;que.push(root);int Depth 0, size 0; // 根节点深度定义为1while (!que.empty()) {Depth;size que.size(); // size必须固定, que.size()是不断变化的for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (node-left NULL node-right NULL) return Depth;if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return Depth;}
};三、递归法 当然这道题也可以用递归法实现。一般的递归法我们需要注意三个点
1、输入参数和返回值2、确定终止条件3、确定单层递归逻辑 找最大深度程序如下程序当中终止条件为节点为NULL返回0表示深度为0。依次寻找左右节点的深度然后当前节点的最大深度为左右节点最大值11是因为算上当前中间节点。
class Solution3 {
public:// 找最大深度int getDepth(TreeNode* root) {if (!root) return 0;int leftdepth getDepth(root-left);int rightdepth getDepth(root-right);int depth 1 max(leftdepth, rightdepth);return depth;}int maxDepth(TreeNode* root) {return getDepth(root);}
};精简版本如下
class Solution3 {
public:// 递归法找最大深度简化版int maxDepth(TreeNode* root) {if (!root) return 0;return 1 max(maxDepth(root-left), maxDepth(root-right));}
};四、完整代码
# include iostream
# include vector
# include queue
# include string
# include algorithm
using namespace std;// 树节点定义
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 maxDepth(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);int Depth 0, size 0; // 根节点深度定义为1while (!que.empty()) {Depth;size que.size(); // size必须固定, que.size()是不断变化的for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (node-left) que.push(node-left);if (node-right) que.push(node-right);} }return Depth;}
};class Solution2 {
public:// 找最小深度int minDepth(TreeNode* root) {if (!root) return 0;queueTreeNode* que;que.push(root);int Depth 0, size 0; // 根节点深度定义为1while (!que.empty()) {Depth;size que.size(); // size必须固定, que.size()是不断变化的for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (node-left NULL node-right NULL) return Depth;if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return Depth;}
};//class Solution3 {
//public:
// // 递归法找最大深度
// int getDepth(TreeNode* root) {
// if (!root) return 0;
// int leftdepth getDepth(root-left);
// int rightdepth getDepth(root-right);
// int depth 1 max(leftdepth, rightdepth);
// return depth;
// }
// int maxDepth(TreeNode* root) {
// return getDepth(root);
// }
//};class Solution3 {
public:// 递归法找最大深度简化版int maxDepth(TreeNode* root) {if (!root) return 0;return 1 max(maxDepth(root-left), maxDepth(root-right));}
};void my_print(vector string v, string msg)
{cout msg endl;for (vectorstring::iterator it v.begin(); it ! v.end(); it) {cout *it ;}cout endl;
}// 前序遍历迭代法创建二叉树每次迭代将容器首元素弹出弹出代码还可以再优化
void Tree_Generator(vectorstringt, TreeNode* node) {if (t[0] NULL || !t.size()) return; // 退出条件else {node new TreeNode(stoi(t[0].c_str())); // 中t.assign(t.begin() 1, t.end());Tree_Generator(t, node-left); // 左t.assign(t.begin() 1, t.end());Tree_Generator(t, node-right); // 右}
}int main()
{vectorstring t { 3, 9, NULL, NULL, 20, 15, NULL, NULL, 7, NULL, NULL}; // 前序遍历my_print(t, 目标树);TreeNode* root new TreeNode();Tree_Generator(t, root);Solution3 s1;int result s1.maxDepth(root);cout 最大深度为 result endl;system(pause);return 0;
}end
