当前位置: 首页 > news >正文

注册公司网上核名网站微商城分销平台免费

注册公司网上核名网站,微商城分销平台免费,宁波专业制作网站,搜索引擎推广效果文章目录二叉树9. 二叉树的最大深度10. 二叉树的最小深度11. 完全二叉树的节点个数12. 平衡二叉树二叉树 9. 二叉树的最大深度 104. 二叉树的最大深度 思路1: 递归找左右子树的最大深度,选择最深的 1(即加上当前层)。 class So…

文章目录

  • 二叉树
    • 9. 二叉树的最大深度
    • 10. 二叉树的最小深度
    • 11. 完全二叉树的节点个数
    • 12. 平衡二叉树

二叉树

9. 二叉树的最大深度

104. 二叉树的最大深度

思路1:
递归找左右子树的最大深度,选择最深的 + 1(即加上当前层)。

class Solution {
public:int maxDepth(TreeNode* root) {if (root == NULL) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}
};

思路2:
利用队列层序遍历二叉树,找到最大深度

class Solution {
public:int maxDepth(TreeNode* root) {int depth = 0;if (root == NULL) return depth;queue<TreeNode *> que;que.push(root);while (!que.empty()) {int size = que.size();depth++;while (size--) {TreeNode *cur = que.front(); que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return depth;}
};

10. 二叉树的最小深度

111. 二叉树的最小深度

思路1: 递归法
要注意只有一个子节点的情况不能统计深度,因为它不是叶子节点。深度是指根节点到叶子节点的距离。

class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;// 下面的两个判断避免了非叶子节点的情况if (!root->left && root->right) return minDepth(root->right) + 1;if (root->left && !root->right) return minDepth(root->left) + 1;return min(minDepth(root->left), minDepth(root->right)) + 1;}
};

思路2:
利用迭代法层序遍历,遇到第一个叶子节点返回深度。

class Solution {
public:int minDepth(TreeNode* root) {if (root == NULL) return 0;queue<TreeNode *> que;int depth = 0;que.push(root);while (!que.empty()) {depth++;int size = que.size();while (size--) {TreeNode *cur = que.front(); que.pop();if (!cur->left && !cur->right) return depth;if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return depth;}
};

11. 完全二叉树的节点个数

222. 完全二叉树的节点个数

思路:
满二叉树的节点数目等于 2depth−12^{depth} - 12depth1 ,利用该条件来避免遍历整个满二叉树,只需要遍历其最左最右两分支的深度即可(O(logn)O(logn)O(logn))。遍历二叉树的递归层数 O(logn)O(logn)O(logn) 。时间复杂度是 O(logn∗logn)O(logn*logn)O(lognlogn)

class Solution {
public:int countNodes(TreeNode* root) {if (root == NULL) return 0;// 利用满二叉树的特性优化时间复杂度TreeNode *curL = root->left;TreeNode *curR = root->right;int depthL = 0;int depthR = 0;while (curL != NULL) {curL = curL->left;depthL++;}while (curR != NULL) {curR = curR->right;depthR++;}if (depthL == depthR) return (2 << depthL) - 1;return countNodes(root->left) + countNodes(root->right) + 1;}
};

12. 平衡二叉树

110. 平衡二叉树

思路1: 递归
后序遍历统计左右子树的高度,比较左右子树高度是否满足条件。

class Solution {
public:bool isBalanced(TreeNode* root) {if (root == NULL) return true;return getHigh(root) == -1 ? false : true;}private:int getHigh(TreeNode *root) {if (root == NULL) return 0;int leftDepth = getHigh(root->left);if (leftDepth == -1) return -1;int rightDepth = getHigh(root->right);if (rightDepth == -1) return -1;if (abs(leftDepth - rightDepth) > 1) return -1; // 如果已经找到不满足底子树,就没必要再遍历了。剪枝return max(leftDepth, rightDepth) + 1;}
};

思路2: 迭代法
用栈模拟递归实现后续遍历统计二叉树深度。
再先序遍历判断左右子树深度是否满足条件。
这里没法剪枝,复杂度并不优秀。

class Solution {
public:bool isBalanced(TreeNode* root) {if (root == NULL) return true;stack<TreeNode *> stk;stk.push(root);while (!stk.empty()) {TreeNode *cur = stk.top(); stk.pop();if (abs(getHigh(cur->left) - getHigh(cur->right)) > 1) return false;if (cur->right) stk.push(cur->right);if (cur->left) stk.push(cur->left);}return true;}private:int getHigh(TreeNode *root) {if (root == NULL) return 0;stack<TreeNode *> stk;int depth = 0, result = 0;stk.push(root);while (!stk.empty()) {TreeNode *cur = stk.top(); stk.pop();if (cur) { // 后序遍历:左右中stk.push(cur); // 中stk.push(NULL);depth++;if (cur->right) stk.push(cur->right); // 右if (cur->left) stk.push(cur->left); // 左} else {cur = stk.top(); stk.pop();depth--; // 回溯}result = result > depth ? result : depth;}return result;}
};
http://www.yayakq.cn/news/53266/

相关文章:

  • 什么好的主题做网站福建建设执业注册中心网站
  • 想自己做淘宝有什么网站吗怎样买空间做网站
  • 网站建设5000费用预算峰聘网360建筑网
  • 怎样提高网站打开速度慢手机传奇网站模板下载
  • 企业官方网站有哪些深圳网站多少钱一年
  • 移动端网站怎么提交济南自助建站模板
  • 怎么看网站用什么代码做的带后台的网站模板
  • 外贸网站下载南阳手机网站建设
  • 购买网站域名怎么做会计分录教育企业网站源码
  • 研究生网站 建设 需求北京 网站建设 知乎
  • 资产管理公司网站建设方案山东省品牌建设促进会网站
  • 做miui主题网站团员关系没转就作废吗
  • 企业快速建站的公司对于协会的新年祝贺语网站模板
  • 网站建设公司广东手机网站建设的第一个问题
  • 券多多是谁做的网站wordpress图片站模板
  • 汕头企业网站建设设计工程公司起名大全字库
  • 网站建设费的摊销如何在百度打广告
  • wordpress 企业网站制作通辽做网站制作
  • 未明潮网站建设保密协议百度权重4网站值多少钱
  • 天猫网站建设目的软件开发外包服务公司
  • 做网站gzip压缩公司网站域名注册费用
  • 随州网站seo多少钱企业主页怎么写
  • ppt做书模板下载网站有哪些内容政协系统网站建设
  • 网站备案 收费wordpress 编辑插件下载
  • 解聘 人力资源网站上怎么做网站制作要花多少钱
  • 企业网站的建立步骤接收外国电视卫星天线
  • 漯河小学网站建设网站推广方案策划书
  • 诚信网站费用福建seo排名
  • 公司禁用网站怎么做学校网站建设情况汇报
  • 广州网站建设哪家比较好个人视频网站注册平台