【LeetCode Cookbook(C++ 描述)】一刷二叉树综合(上)

目录

  • LeetCode #226:Invert Binary Tree 翻转二叉树
    • 「遍历」
    • 「分而治之」
    • 广度优先搜索:层序遍历
  • LeetCode #101:Symmetric Tree 对称二叉树
    • 递归法
    • 迭代法
  • LeetCode #100:Same Tree 相同的树
    • 递归法
    • 迭代法
  • LeetCode #559:Maximum Depth of N-ary Tree - N 叉树的最大深度
    • 递归法之「分而治之」
    • 递归法之「遍历」
    • 迭代法
  • LeetCode #111:Minimum Depth of Binary Tree 二叉树的最小深度
    • 递归法之「分而治之」
    • 递归法之「遍历」
    • 迭代法(BFS)
  • LeetCode #222:Count Complete Tree Nodes 完全二叉树的节点个数
    • 利用二分查找与位运算的解法(LeetCode 官解)

本系列文章仅是 GitHub 大神 @halfrost 的刷题笔记 《LeetCode Cookbook》的提纲以及示例、题集的 C++转化。原书请自行下载学习。
本篇文章涉及新手应该优先刷的几道经典二叉树综合算法题。

❗️二叉树解题的思维模式分两类

  1. 是否可以通过遍历一遍二叉树得到答案?如果可以,用一个 traverse() 函数配合外部变量来实现,这叫「遍历」的思维模式。
  2. 是否可以定义一个递归函数,通过子问题(子树)的答案推导出原问题的答案?如果可以,写出这个递归函数的定义,并充分利用这个函数的返回值,这叫「分而治之」的思维模式。

无论使用哪种思维模式,你都需要思考:

如果单独抽出一个二叉树节点,它需要做什么事情?需要在什么时候(前/中/后序位置)做?我们不需要考虑其他节点,递归函数会在所有节点上执行相同的操作。

LeetCode #226:Invert Binary Tree 翻转二叉树

#226
翻转一棵二叉树,就是将每个节点的左右子节点进行交换,最后的结果就是完全翻转之后的二叉树。

「遍历」

仿照二叉树的递归遍历的代码框架,构造一个 traverse() 方法遍历每个节点,翻转每个节点的左右子节点。因此,对于单个节点,只需要交换自身的子节点即可

TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;

利用 DFS 递归,层层深入,最终将整棵树的全部节点翻转,核心的针对单个节点的代码放在任意位置均可,这里放在了前序位置;当然,直接将核心代码移到中序位置——不同于前后序位置——是有问题的,交换了左右子树后,左右子树已经换了位置,递归右子树即为递归之前的左子树,因此使用中序位置遍历的顺序应为:递归左子树、交换左右子树、递归左子树

class Solution {
public:TreeNode* invertTree(TreeNode* root) {//遍历二叉树,交换每个节点的子节点if (root != nullptr) traverse(root);return root;}private:void traverse(TreeNode* root) {if (root != nullptr) {//遍历框架,去遍历左右子树的节点traverse(root->left);// *** 中序位置 ***//每一个节点需要做的事就是交换它的左右子节点TreeNode* temp = root->left;root->left = root->right;root->right = temp;traverse(root->left);  //注意!}}
};

该算法的时间复杂度为 O ( n ) \ O(n)  O(n) ,空间复杂度为 O ( n ) \ O(n)  O(n)

「分而治之」

我们为 invertTree() 函数赋予定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点。我们需要考虑的是,对于某一个二叉树节点 root 执行 invertTree(root) 方法,可以利用这一定义实现什么功能?

利用 invertTree(root->left) 方法先把 root 的左子树翻转,再利用 invertTree(root->right) 方法将其右子树翻转,最后将 root 的左右子树交换,即完成整棵二叉树的翻转,这就是分治的思想。

class Solution {
public://定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点TreeNode* invertTree(TreeNode* root) {if (root == nullptr) return nullptr;//翻转左右子树TreeNode* left = invertTree(root->left);TreeNode* right = invertTree(root->right);//交换左右子节点root->left = right;root->right = left;//和定义逻辑自洽:以 root 为根的这棵二叉树已经被翻转,返回 rootreturn root;}
};

这种「分而治之」的思路,核心在于给递归函数一个合适的定义,然后用函数的定义来解释代码;如果代码逻辑成功自洽,那么说明这一代码所表达的算法是正确的。

广度优先搜索:层序遍历

既然可以通过递归(顺序)遍历来实现,那么也可以通过层序遍历来实现。使用队列存储需要处理的节点,在循环中不断地从队列中取出节点并检查它的左右子节点——如果子节点不为空,我们将其添加到队列中,并在之后交换当前节点的左右子节点。

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == nullptr) return nullptr;queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* node = q.front();q.pop();//处理左子树TreeNode* left = node->left;if (left != nullptr) q.push(left);//处理右子树TreeNode* right = node->right;if (right != nullptr) q.push(right);//交换左右子节点node->left = right;node->right = left;}return root;}
};

LeetCode #101:Symmetric Tree 对称二叉树

#101
给定一个二叉树,检查它是否是镜像对称的。

实际上,所谓「镜像对称」就是左右子树是否相互翻转,那么只需要左子树的左节点和右子树的右节点、左子树的右节点和右子树的左节点比较即可。

递归法

对于每一层来说,我们比较的都是左子树的左节点和右子树的右节点、左子树的右节点和右子树的左节点是否相等。换言之,我们本质上是在比较两棵树是否对称。因此,由于需要相互进行对比,线性且单一的「遍历」思路就行不通了,我们只能采用「分而治之」的思想。

进一步地,由于我们需要不断地比对 root 的左右子树,引进辅助函数 isMirror(TreeNode* left, TreeNode* right) 来传入两个参数进行递归比对并返回布尔值。

return isMirror(left->left, right->right) && isMirror(left->right, right->left);

显然,我们需要确定终止条件base case )。

首先,节点为空时,分为 3 种情况:

  • 左右节点都为空,此时相当于只有一个头节点,是对称的。
  • 左节点为空,右节点不为空,显然不对称。
  • 左节点不为空,右节点为空,显然也是不对称的。

其次,节点非空时,只需要比较两个节点的值是否相等,相等则对称,反之则不对称。

基本上,整个算法就成形了:

class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == nullptr) return true;return isMirror(root->left, root->right);}private:bool isMirror(TreeNode* left, TreeNode* right) {//如果两个节点都为空,则它们是镜像对称的if (left == nullptr && right == nullptr) return true;//如果只有一个为空,或者节点的值不等,则它们不是镜像对称的if (((left == nullptr) != (right == nullptr)) || left->val != right->val) return false;//递归地检查左子树的左节点和右子树的右节点,以及左子树的右节点和右子树的左节点return isMirror(left->left, right->right) && isMirror(left->right, right->left);}
};

该算法的时间复杂度为 O ( n ) \ O(n)  O(n) ,空间复杂度为 O ( n ) \ O(n)  O(n)

迭代法

类似于基于广义优先搜索的层序遍历,模拟递归的底层逻辑,构造一个队列,每次将当前层的节点,按照左子树的左节点和右子树的右节点、左子树的右节点和右子树的左节点放入队列,再依次两两出队列,比较数值是否相等

class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == nullptr) return true;//初始化队列queue<TreeNode*> q;q.push(root->left);q.push(root->right);while (!q.empty()) {//从队列中取出两个节点TreeNode* left = q.front(); q.pop();TreeNode* right = q.front(); q.pop();//若两个节点都为空,则继续循环if (left == nullptr && right == nullptr) continue;//其中一个节点为空,或者左右节点的值不等,则不对称if (((left == nullptr) != (right == nullptr)) || (left->val != right->val)) return false;//左子树的左节点和右子树的右节点入队列q.push(left->left);q.push(right->right);//左子树的右节点和右子树的左节点入队列q.push(left->right);q.push(right->left);}return true;}
};

LeetCode #100:Same Tree 相同的树

#100
给定两棵二叉树的根节点 pq ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为他们是相同的。

这道题与上一题 #101 类似,#101 题本质上就是在维护两棵树,只不过这道题是实实在在的两棵树罢了,甚至这道题更为简单,我们无需引入辅助函数。

递归法

我们仍然需要运用「分而治之」的思维模式。只需要判断 p 树的左子树和 q 树的左子树、p 树的右子树和 q 树的右子树是否相等即可。

class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {//判断一对节点是否相同if (p == nullptr && q == nullptr) return true;if (((p == nullptr) != (q == nullptr)) || (p->val != q->val)) return false;//判断其他节点是否相同return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}
};

假设 p 树有 m \ m  m 个节点,q 树有 n \ n  n 个节点,该算法的时间复杂度和空间复杂度均为 O ( m i n ( m , n ) ) \ O(min(m, n))  O(min(m,n))

迭代法

对于每一层来说,只要 p 树和 q 树的对应节点存在且相等即可,类似于层次遍历,使用队列来解决——每次将 p 树和 q 树对应层的节点依次入队列,取出前两个元素弹出队列进行比较,再依次将 p 的左节点和 q 的左节点、p 的右节点和 q 的右节点入队列,……,直至队列为空,遍历结束。

class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {//初始化队列std::queue<TreeNode*> queue;queue.push(p);queue.push(q);while (!queue.empty()) {//从队列中取出两个节点TreeNode* p_Node = queue.front(); queue.pop();TreeNode* q_Node = queue.front(); queue.pop();//若当前为空,则继续循环if (p_Node == nullptr && q_Node == nullptr) continue;//如果其中一个节点为空,另一个不为空,或者值不等,则一定不相同if (((p_Node == nullptr) != (q_Node == nullptr)) || p_Node->val != q_Node->val) return false;// p_Node 节点的左孩子和 q_Node 节点的左孩子入队列queue.push(p_Node->left);queue.push(q_Node->left);// p_Node 节点的右孩子和 q_Node 节点的右孩子入队列queue.push(p_Node->right);queue.push(q_Node->right);}//如果所有节点都匹配,则返回truereturn true;}
};

LeetCode #559:Maximum Depth of N-ary Tree - N 叉树的最大深度

#559
给定一个 N 叉树,找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

先前解决了二叉树的最大深度问题,我们再进一步推广到 N 叉树最大深度问题。

递归法之「分而治之」

首先我们应当找出重复的子问题,即找出单一子树的最大深度,那么对于其他子树也是同样的操作,利用递归逐层实现并比较各子树的最大深度。

for (Node* child : root->children) subTreeMaxDepth = max(subTreeMaxDepth, maxDepth(child));

其次,确定递归终止条件 base caseroot == nullptr ,递归终止后 N 叉树的最大深度应为 subTreeMaxDepth + 1

class Solution {
public:int maxDepth(Node* root) {if (root == nullptr) return 0;int subTreeMaxDepth = 0;for (Node* child : root->children) subTreeMaxDepth = max(subTreeMaxDepth, maxDepth(child));return subTreeMaxDepth + 1;}
};

该算法的时间复杂度为 O ( n ) \ O(n)  O(n) ,空间复杂度为 O ( n ) \ O(n)  O(n)

递归法之「遍历」

我们很容易从二叉树的遍历框架推广到 N 叉树的情况,只需要更改核心代码对于树的操作即可,traverse() 辅助函数的基本架构不变。

class Solution {
public:int maxDepth(Node* root) {traverse(root);return res;}private://记录递归遍历到的深度int depth = 0;//记录最大的深度int res = 0;void traverse(Node* root) {if (root == nullptr) return;//前序遍历位置depth++;res = max(res, depth);for (Node* child : root->children) traverse(child);//后序遍历位置depth--;}
};

迭代法

我们也可以利用「广度优先搜索」的原理、层序遍历来解决这道题目,使用队列保存每一层的所有节点,把队列里的所有节点弹出队列,然后把这些被弹出的节点各自的子节点入队列。用 depth 维护每一层,此时我们广度优先搜索的队列里存放的是当前层的所有节点

不同于广度优先搜索的每次只从队列里拿出一个节点,我们需要将队列里的所有节点都拿出来进行拓展,这样能保证我们是一层层地进行拓展的。该 N 叉树的最大深度即为 depth

class Solution {
public:int maxDepth(Node* root) {//如果根节点为空,则树的深度为0if (root == nullptr) return 0;//使用队列进行层次遍历queue<Node*> q;q.push(root);   //将根节点加入队列int depth = 0;   //初始化深度为 0 //当队列不为空时,继续遍历while (!q.empty()) {//当前层的节点数等于队列的大小int n = q.size();//遍历当前层的所有节点for (int i = 0; i < n; i++) {Node* node = q.front(); // 从队列中取出一个节点q.pop(); // 弹出该节点//遍历当前节点的所有子节点,并将它们加入队列for (Node* child : node->children) {q.push(child); // 将子节点加入队列以便后续处理}}//每处理完一层,深度加 1depth++;}//返回树的最大深度return depth;}
};

LeetCode #111:Minimum Depth of Binary Tree 二叉树的最小深度

#111
给定一个二叉树,找出其最小深度。

最小深度是从根节点到叶子节点的最短路径上的节点数量。

递归法之「分而治之」

每次先遍历左子树,找出左子树的最小深度,再遍历右子树,找出右子树的最小深度,最终再取左子树和右子树最小深度的最小值,加上根节点的高度 1,即 min(leftMindepth, rightMindepth) + 1 为当前二叉树的最小深度;特别地,我们需要注意特殊情况,若节点缺少其中一支(左节点或右节点),这棵由该节点组成的二叉树的最小深度应为 2 而非 1 。

class Solution {
public:int minDepth(TreeNode* root) {// base caseif (root == nullptr) return 0;//递归计算左子树的最小深度int leftDepth = minDepth(root->left);//递归计算右子树的最小深度int rightDepth = minDepth(root->right);//特殊情况处理:如果左子树为空,返回右子树的深度加 1if (leftDepth == 0) return rightDepth + 1;//特殊情况处理:如果右子树为空,返回左子树的深度加 1if (rightDepth == 0) return leftDepth + 1;//以上分两类讨论特殊情况的代码可以合并为// if (leftDepth == 0 || rightDepth == 0) return leftDepth + rightDepth + 1;//计算并返回最小深度:左右子树深度的最小值加 1return min(leftDepth, rightDepth) + 1;}
};

该算法的时间复杂度为 O ( n ) \ O(n)  O(n) ,空间复杂度为 O ( n ) \ O(n)  O(n)

递归法之「遍历」

递归调用 traverse() 方法回溯遍历整棵二叉树,先做选择,在进入节点时,将 currentDepth 增加 1,再检查叶子节点,如果当前节点是叶子节点(即没有左子节点和右子节点),则将其深度与 minDepthValue 进行比较,并更新 minDepthValue 为两者中的较小值。根据这一流程,递归地遍历左子树和右子树。最后在树的末端撤销选择,离开节点时将 currentDepth 减少 1,以恢复到父节点的深度,确保在遍历其他分支时,currentDepth 能够正确地反映当前节点的深度

class Solution {
public:int minDepth(TreeNode* root) {if (root == nullptr) return 0;traverse(root);return minDepthValue;}private:int minDepthValue = INT_MAX;int currentDepth = 0;void traverse(TreeNode* root) {if (root == nullptr) return;  // base case//做选择:在进入节点时增加当前深度currentDepth++;//如果当前节点是叶子节点,更新最小深度if (root->left == nullptr && root->right == nullptr) minDepthValue = min(minDepthValue, currentDepth);traverse(root->left);traverse(root->right);//撤销选择:在离开节点时减少当前深度currentDepth--;}
};

迭代法(BFS)

与层序遍历类似,使用队列保存每一层的所有节点,把队列里的所有节点依次弹出队列,当出队列的节点为叶子节点,立即返回当前层数,即为最小深度,否则把这些被弹出的节点各自的子节点(即下一层节点)入队列。用 depth 维护每一层。

class Solution {
public:int minDepth(TreeNode* root) {if (root == nullptr) return 0;queue<TreeNode*> q;q.push(root);// root 本身就是一层,depth 初始化为 1int depth = 1;while (!q.empty()) {int levelSize = q.size();//遍历当前层的节点for (int i = 0; i < levelSize; i++) {TreeNode* cur = q.front();q.pop();//判断是否到达叶子节点if (cur->left == nullptr && cur->right == nullptr) return depth;//将下一层节点加入队列if (cur->left != nullptr) q.push(cur->left);if (cur->right != nullptr) q.push(cur->right);}//增加步数depth++;}return depth;}
};

LeetCode #222:Count Complete Tree Nodes 完全二叉树的节点个数

#222
给你一棵完全二叉树的根节点 root ,求出该树的节点个数。

如果是一棵普通二叉树,完全可以套用遍历框架进行循环累积,时间复杂度为 O ( n ) \ O(n)  O(n)

int countNodes(TreeNode* root) {if (root == nullptr) return 0;return countNodes(root->left) + countNodes(root->right) + 1;
}

如果是一棵满二叉树,节点个数与树的高度1呈指数关系 n = 2 h − 1 \ n = 2^h - 1  n=2h1

int countNodes(TreeNode* root) {int h = 0;//计算树的深度while (root != nullptr) {root = root->left;h++;}// return pow(2, h) - 1;return (1 << h) - 1;
}

但正如题目所要求的,我们的算法时间复杂度必须低于 O ( n ) \ O(n)  O(n) ,我们需要进一步优化我们对于完全二叉树的算法。此时,回归概念本质,同时将复杂问题划分为基本可处理的简单问题是非常关键的——所谓「完全二叉树」,其除了最底层以外,其余的每一层节点数都是满的,且最底层的节点全集中在该层最左边的位置,这就很明显地表明,对于一棵完全二叉树,左子树的高度必然大于等于右子树的高度

  • 当左子树的高度等于右子树的高度时,左子树必定是满二叉树。
  • 当左子树的高度大于右子树的高度时,右子树必定是满二叉树。
Full Binary Tree
Full Binary Tree
Full Binary Tree
Right
left->left
left
left->right
right->left
root
right
Root
Left
Left->left
Left->right

也就是,一棵完全二叉树的两棵子树,至少有一棵是满二叉树

经过这样的转化,我们就可以将部分子树看作是满二叉树,套用相关的节点公式 n = 2 h − 1 \ n = 2^h - 1  n=2h1 即可得出该子树的节点个数;至于剩余子树,直接递归解决。

class Solution {
public:int countNodes(TreeNode* root) {TreeNode* left = root, *right = root;//沿最左侧和最右侧分别计算高度int leftHeight = 0, rightHeight = 0;while (left != nullptr) {left = left->left;leftHeight++;}while (right != nullptr) {right = right->right;rightHeight++;}//如果左右侧计算的高度相同,则是一棵满二叉树if (leftHeight == rightHeight) return (1 << leftHeight) - 1;//如果左右侧的高度不同,则按照普通二叉树的逻辑计算return 1 + countNodes(root->left) + countNodes(root->right);}
};

由于完全二叉树的性质,其子树一定有一棵是满的,所以一定会触发 leftHeight == rightHeight ,只消耗 O ( log ⁡ n ) \ O(\log n)  O(logn) 的复杂度而不会继续递归。

综上,算法的递归深度就是树的高度 O ( log ⁡ n ) \ O(\log n)  O(logn),每次递归所花费的时间就是 while 循环,需要 O ( log ⁡ n ) \ O(\log n)  O(logn),所以总体的时间复杂度是 O ( log ⁡ 2 n ) \ O(\log^2 n)  O(log2n);此外,使用了递归,额外调用了栈空间,空间复杂度为 O ( log ⁡ n ) \ O(\log n)  O(logn)

利用二分查找与位运算的解法(LeetCode 官解)

规定根节点位于第 0 层,完全二叉树的最大层数为 h \ h  h 。根据完全二叉树的特性可知,完全二叉树的最左边的节点一定位于最底层,因此从根节点出发,每次访问左子节点,直到遇到叶子节点,该叶子节点即为完全二叉树的最左边的节点,经过的路径长度即为最大层数 h \ h  h

0 ≤ i < h \ 0≤i<h  0i<h 时,第 i \ i  i 层包含 2 i \ 2^i  2i 个节点,最底层包含的节点数最少为 1,最多为 2 h \ 2^h  2h

最底层包含 1 个节点时,完全二叉树的节点个数
∑ i = 0 h − 1 2 i + 1 = 2 0 + 2 1 + 2 2 + . . . + 2 h − 1 + 1 = 2 h − 1 + 1 = 2 h \sum\limits_{i = 0}^{h - 1} 2^{i} + 1 = 2^0 + 2^1 + 2^2 + ... + 2^{h-1} + 1 = 2^h - 1 + 1 = 2^h i=0h12i+1=20+21+22+...+2h1+1=2h1+1=2h

当最底层包含 2 h \ 2^h  2h 个节点时,完全二叉树的节点个数
∑ i = 0 h 2 i = 2 h + 1 − 1 \sum\limits_{i = 0}^{h} 2^{i} = 2^{h+1} - 1 i=0h2i=2h+11

因此对于最大层数为 h \ h  h 的完全二叉树,节点个数一定在 [ 2 h , 2 h + 1 − 1 ] \ [2^h, 2^{h+1} − 1]  [2h,2h+11] 的范围内,我们可以先找到树的最深左子树的高度,在该范围内通过二分查找的方式得到完全二叉树的节点个数的精确解。

具体的做法是,根据节点个数范围的上下界得到当前需要判断的节点个数 k \ k  k ,如果第 k \ k  k 个节点存在,则节点个数一定大于或等于 k \ k  k ,如果第 k \ k  k 个节点不存在,则节点个数一定小于 k \ k  k ,由此可以将查找的范围缩小一半,直到得到节点个数。

为判断 k \ k  k 个节点是否存在,我们定义一个辅助函数 exist() ,如果第 k \ k  k 个节点位于第 h \ h  h 层,则 k \ k  k 的二进制表示包含 h + 1 \ h+1  h+1 位,其中最高位是 1,其余各位从高到低表示从根节点到第 k 个节点的路径,0 表示移动到左子节点,1 表示移动到右子节点。通过位运算得到第 k \ k  k 个节点对应的路径,判断该路径对应的节点是否存在,即可判断第 k \ k  k 个节点是否存在。

转自 LeetCode

class Solution {
public:int countNodes(TreeNode* root) {//如果根节点为空,则树中没有节点if (root == nullptr) return 0;//找到左子树的高度int level = 0;TreeNode* node = root;while (node->left != nullptr) {level++;node = node->left;}//确定节点个数的区间范围int low = 1 << level, high = (1 << (level + 1)) - 1;//使用二分查找确定当前树在第 level 层的实际节点数while (low < high) {//计算中间位置(偏向 high 端,因为实际存在的节点数可能接近 high)int mid = (high - low + 1) / 2 + low;//如果 mid 位置存在节点,则更新 low 为 mid,否则更新 high 为 mid - 1if (exists(root, level, mid)) low = mid;else high = mid - 1;}// 当 low == high 时,找到了最深层实际存在的节点数,即为整棵树的节点总数return low;}//辅助函数,用于判断在第 level 层的第 k 个位置(从 1 开始计数)是否存在节点//利用了二叉树的性质,通过 k 的二进制表示来导航到目标节点bool exists(TreeNode* root, int level, int k) {// bits用于从 k 的二进制表示中逐位提取信息int bits = 1 << (level - 1);TreeNode* node = root;//遍历 k 的每一位(从最高位到最低位)while (node != nullptr && bits > 0) {//如果当前位是 0,则向左子树移动if (!(bits & k)) node = node->left;else node = node->right;    //如果当前位是 1,则向右子树移动//准备检查下一位bits >>= 1;}//如果最终 node 不为空,说明找到了目标节点return node != nullptr;}
};

对于该算法的时间复杂度,首先需要 O ( h ) \ O(h)  O(h) 的时间得到完全二叉树的最大深度,其中 h \ h  h 是完全二叉树的最大深度(高度)。使用二分查找确定节点个数时,需要查找的次数为 O ( log ⁡ 2 h ) = O ( h ) \ O(\log^2 h) = O(h)  O(log2h)=O(h),每次查找需要遍历从根节点开始的一条长度为 h \ h  h 的路径,需要 O ( h ) \ O(h)  O(h) 的时间,因此二分查找的总时间复杂度是 O ( h 2 ) \ O(h^2)  O(h2)

由此,总时间复杂度是 O ( h 2 ) \ O(h^2)  O(h2)。由于完全二叉树满足 2 h ≤ n < 2 h + 1 \ 2^h ≤ n < 2^{h+1}  2hn<2h+1,因此有 O ( h ) = O ( log ⁡ n ) \ O(h) = O(\log n)  O(h)=O(logn) O ( h 2 ) = O ( log ⁡ 2 n ) \ O(h^2) = O(\log^2 n)  O(h2)=O(log2n)

只需要维护有限的额外空间,空间复杂度为 O ( 1 ) O(1) O(1)

呜啊?


  1. 在二叉树中,“深度”通常指的是从根节点到某个节点的最长路径上的边数,而“高度”指的是从该节点到叶子节点的最长路径上的边数;也就是说,“高度”是所谓“最大深度”。 ↩︎

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/400993.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

八种排序算法的复杂度(C语言)

归并排序(递归与非递归实现,C语言)-CSDN博客 快速排序(三种方法,非递归快排,C语言)-CSDN博客 堆排序(C语言)-CSDN博客 选择排序(C语言)以及选择排序优化-CSDN博客 冒泡排序(C语言)-CSDN博客 直接插入排序(C语言)-CSDN博客 希尔排序( 缩小增量排序 )(C语言)-CSDN博客 计数…

赋能基层,融合创新:EasyCVR视频汇聚平台构建平安城市视频共享系统

一、雪亮工程建设的意义 雪亮工程的核心在于通过高清视频监控、环境监测和智能预警等先进技术手段&#xff0c;构建一个高效、智能、安全、便捷的社会安全防控体系。这一工程的建设不仅代表了现代化科技手段在城市治安管理中的应用&#xff0c;更是提升社会安全保障能力、推动…

LeetCode.3152.特殊数组II

题目描述&#xff1a; 如果数组的每一对相邻元素都是两个奇偶性不同的数字&#xff0c;则该数组被认为是一个 特殊数组 。 你有一个整数数组 nums 和一个二维整数矩阵 queries&#xff0c;对于 queries[i] [fromi, toi]&#xff0c;请你帮助你检查 子数组 nums[fromi..toi…

纷享销客CRM AI产品架构概览、产品特色

一、纷享销客CRM AI产品架构概览 纷享AI平台架构分为三个主要层次&#xff1a;AI基础设施层、AI平台层和AI应用层。每个层次都由一系列功能模块组成&#xff0c;旨在为客户提供强大的技术支持和灵活的解决方案。 1.Al基础设施层 AI基础设施层是整个AI平台的底层支撑&#xff…

使用WooCommerce订阅续订进行货到付款:自定义订单状态

WooCommerce订阅插件允许商店设置周期性的订阅产品。客户购买订阅后&#xff0c;系统会自动根据设定周期进行续订。但对于货到付款的场景&#xff0c;自动续订就面临挑战。 自定义订单状态 为了实现货到付款的续订流程&#xff0c;我们需要创建一个自定义订单状态。以下是具体…

牛客刷题总结——Python入门07:内置函数

🤵‍♂️ 个人主页: @北极的三哈 个人主页 👨‍💻 作者简介:Python领域优质创作者。 📒 系列专栏:《牛客题库-Python篇》 🌐推荐《牛客网》——找工作神器|笔试题库|面试经验|实习经验内推,求职就业一站解决 👉 点击链接进行注册学习 文章目录 010 内置函…

鸿蒙开发入门day06-ArkUI简介

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;还请三连支持一波哇ヾ(&#xff20;^∇^&#xff20;)ノ&#xff09; 目录 ArkUI简介 基本概念 两种开发范式 不同应用类型支持的开发范式 …

Linux--应用层协议HTTP协议(http服务器构建)

目录 1.HTTP 协议 2.认识 URL 3.urlencode 和 urldecode&#xff08;编码&#xff09; urlencode&#xff08;URL编码&#xff09; urldecode&#xff08;URL解码&#xff09; 4.HTTP 协议请求与响应格式 4.1HTTP 常见方法&#xff08;三种&#xff09; 5.HTTP 的状态码…

如何妙用哈希表来优化遍历查找过程?刷题感悟总结,c++实现

先上题目 题目链接&#xff1a;题目链接 这题我最先想到的就是前缀和a&#xff0c;构造好了以后就遍历每一个[l,r]数组&#xff08;满足题目要求的连续区间数组&#xff09;&#xff0c;奈何倒数第二个样例时间超限 先给出原思路代码 class Solution { public:int subarray…

【深入理解SpringCloud微服务】Ribbon源码解析

【深入理解SpringCloud微服务】Ribbon源码解析 Ribbon的原理RestTemplate中的拦截器链Ribbon的拦截器如何将拦截器放入到RestTemplate中 Ribbon中的核心类LoadBalancerAutoConfigurationLoadBalancerInterceptorLoadBalancerClientILoadBalancerServerListIRuleIPing Ribbon核心…

【高性能高易用】物联网AI开发套件----Qualcomm® RB3 Gen 2 开发套件

Qualcomm RB3 Gen 2 开发套件 专为高性能计算、高易用性而设计的物联网开发套件 Qualcomm RB3 Gen 2 开发套件拥有先进的功能和强大的性能&#xff0c;包括强大的AI运算&#xff0c;12 TOPS 算力和计算机图形处理能力&#xff0c;可轻松创造涵盖机器人、企业、工业和自动化等…

【nginx 第一篇章】认识一下 NGINX 服务器

一、简介 Nginx (engine x) 是一个高性能的 HTTP 和反向代理服务器&#xff0c;也是一个 IMAP/POP3/SMTP 代理服务器。由俄罗斯程序员 Igor Sysoev 开发&#xff0c;并在2004年首次公开发布。Nginx 以其高并发处理能力、低内存消耗、稳定性、丰富的功能集、简单的配置以及低学…

HarmonyOS应用三之组件生命周期和参数传递

目录&#xff1a; 1、生命周期的执行顺序2、页面数据传递3、图片的读取4、数据的备份和恢复5、轮播图6、页面布局图 1、生命周期的执行顺序 /** Copyright (c) 2023 Huawei Device Co., Ltd.* Licensed under the Apache License, Version 2.0 (the "License");* yo…

html+css 实现hover 换背景跳动按钮

前言:哈喽,大家好,今天给大家分享html+css 实现hover 换背景跳动按钮!并提供具体代码帮助大家深入理解,彻底掌握!创作不易,如果能帮助到大家或者给大家一些灵感和启发,欢迎收藏+关注哦 💕 目录 📚一、效果📚二、原理解析💡这个按钮hover后,有4个变化:📝1.1…

⼆叉树选择题

⼆叉树选择题 本篇文章是初阶二叉树的收尾&#xff0c;旨在进一步加深对于二叉树性质的理解&#xff0c;祝你有一个愉快的学习之旅&#xff01; &#x1f4a1; ⼆叉树性质 1&#xff09;对任何⼀棵⼆叉树, 如果度为 0 其叶结点个数为 n0 , 度为 2 的分⽀结点个数为 n2 ,则有…

Java 阿里云视频直播开发流程

首先来看一下直播效果 推流工具有很多种&#xff08;例如OBS、阿里云直播Demo推流、等等&#xff0c;我用的是芯象导播&#xff09;阿里播放器地址 一、直播基础服务概述 官方文档说明 二、直播域名配置需要两个域名&#xff08;推流域名、播流域名&#xff09; 官方文档说…

haproxy七层代理总结

一、HAProxy概念 1.1 什么是HAProxy&#xff1f; HAProxy是一款开源、高性能的负载均衡器和代理服务器&#xff0c;专为TCP和HTTP应用而设计。它可以将客户端的请求分发到多台后端服务器&#xff0c;从而提高应用的可用性和性能。HAProxy支持多种负载均衡算法和健康检查机制&a…

Python 3 入门基础知识【3】递归函数以及参数部分

在编码过程中除了使用Python内置的函数以外&#xff0c;我们也经常需要自己定义函数。今天来回顾python中的函数。 目录 1.定义函数 2.中函数的返回值 3.递归函数 4.Python函数参数 5.Python函数使用默认参数 6.Python函数使用可变参数 7.Python函数使用可变关键字参数 …

针对thinkphp站点的漏洞挖掘和经验分享

0x1 前言 浅谈 目前在学习和研究thinkphp相关漏洞的打法&#xff0c;然后最近对于thinkphp资产的收集方面有了一个简单的认识&#xff0c;然后写一篇新手看的thinkphp相关的漏洞收集和挖掘的文章来分享下。然后后面是给师傅们分享下后台文件上传&#xff0c;然后直接打一个ge…

WPF 资源、引用命名空间格式、FrameworkElement、Binding、数据绑定

资源 对象级别独立文件 静态资源使用(StaticResource)指的是在程序载入内存时对资源的一次性使用&#xff0c;之后就不再去访问这个资源了。 动态资源使用&#xff08;DynamicResource&#xff09;使用指的是在程序运行过程中仍然会去访问资源。 显然&#xff0c;如果你确定…