商务网站建设实训报告,网站开发设计知乎,深圳网站建设案,如何做php游戏介绍网站二叉树与递归 前言226.翻转二叉树算法思路及代码solution 1 用分解问题的思路来解决solution 2 用遍历的思路来解决 101.对称二叉树算法思路及代码solution 104.二叉树的最大深度算法思路及代码solution 1 遍历solution 2 分解问题 111.二叉树的最小深度算法思路及代码solution… 二叉树与递归 前言226.翻转二叉树算法思路及代码solution 1 用分解问题的思路来解决solution 2 用遍历的思路来解决 101.对称二叉树算法思路及代码solution 104.二叉树的最大深度算法思路及代码solution 1 遍历solution 2 分解问题 111.二叉树的最小深度算法思路及代码solution 1solution 2 222.完全二叉树的结点个数算法思路和代码solution 1solution 2 110 平衡二叉树算法思路及代码solution 257 二叉树的所有路径算法思路及代码 404 左叶子之和算法思路与代码solution 513 找树左下角的值算法思路及代码solution1 遍历solution 2迭代 112.路径总和算法思路以及代码solution 1暴力 solution 2 106 中序与后序遍历序列构造二叉树思路及代码solution相关题目 654 最大二叉树思路及代码solution 二叉搜索树相关700.二叉搜索树中的搜索算法思路与代码solution 前言
本文是基于代码随想录上二叉树章节的所有例题及其对应的算法思路序号代表的是力扣题号
为了避免很多读者看不到最后 我写在最前面 文章总字数预计超过25000字 制作不易 这些都是我在看了很多视频之后整理而成的 希望先收藏点赞起来 以免后续丢失
算法思路主要参考B站灵神 代码随想录 labuladong 懒猫老师 想象力少年 在此跪谢 所有题目讲解视频都可以在这里找到 视频合集
不知道从哪入手的 参考我的学习顺序
1 懒猫老师的二叉树章节视频2 labuladong二叉树纲领篇3 刷题配合着灵神和官方讲解视频
labuladong二叉树纲领篇——遇到一道二叉树的题目时的通用思考过程是 1、是否可以通过遍历一遍二叉树得到答案如果可以用一个 traverse 函数配合外部变量来实现。 2、是否可以定义一个递归函数通过子问题子树的答案推导出原问题的答案如果可以写出这个递归函数的定义并充分利用这个函数的返回值。 3、无论使用哪一种思维模式你都要明白二叉树的每一个节点需要做什么需要在什么时候前中后序做。
226.翻转二叉树 算法思路及代码
solution 1 用分解问题的思路来解决
是我在没看题解之前自己想出来的方法 我是怎么想的呢 我们既然需要翻转整颗二叉树那么我们不妨先翻转左子树在翻转右子树然后将跟节点的左右子树交换即可这样就好啦 递归的结束条件就是节点为空时结束
solution 2 用遍历的思路来解决
这题我们只需要遍历一遍二叉树就可以解决问题为什么这么说呢 单独抽出来一个结点来 我们只需要交换左右结点 对不对 而且我们需要在往下去递归之前做这件事情也就是在前序位置去交换左右节点 然后其余的结点交给递归就好
/*** 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 1 {
public:TreeNode* invertTree(TreeNode* root) {if(rootnullptr){return nullptr;}TreeNode* right invertTree(root-left);TreeNode* left invertTree(root-right);root-rightright;root-leftleft;return root;}
};
class Solution 2 {
public:// 主函数TreeNode* invertTree(TreeNode* root) {// 遍历二叉树交换每个节点的子节点traverse(root);return root;}// 二叉树遍历函数void traverse(TreeNode* root) {if (root nullptr) {return;}// *** 前序位置 ***// 每一个节点需要做的事就是交换它的左右子节点TreeNode* tmp root-left;root-left root-right;root-right tmp;// 遍历框架去遍历左右子树的节点traverse(root-left);traverse(root-right);}
};101.对称二叉树 算法思路及代码
对于这题 我们先不管代码怎么实现我们是不是同样遍历一遍二叉树就可以把这个问题解决掉 我们只需要每往下遍历以后 比较它的左右子树即可后序位置上
solution
class Solution {
public:bool compare(TreeNode* left, TreeNode* right) {// 首先排除空节点的情况if (left NULL right ! NULL) return false;else if (left ! NULL right NULL) return false;else if (left NULL right NULL) return true;// 排除了空节点再排除数值不相同的情况else if (left-val ! right-val) return false;// 此时就是左右节点都不为空且数值相同的情况// 此时才做递归做下一层的判断bool outside compare(left-left, right-right); // 左子树左、 右子树右bool inside compare(left-right, right-left); // 左子树右、 右子树左bool isSame outside inside; // 左子树中、 右子树中 逻辑处理return isSame;}bool isSymmetric(TreeNode* root) {if (root NULL) return true;return compare(root-left, root-right);}
};104.二叉树的最大深度 算法思路及代码
solution 1 遍历
对于这道题目我们首先是不是同样可以用遍历的思路来解决终止条件就是到达叶子节点我们只需要一个traverse函数和一个外部变量来实现就行在刚刚进入一个结点的时候前序位置去更新我们的maxdepth在离开一个节点之前后序位置去维护depth。
class Solution {public:int depth 0;int res 0;int maxDepth(TreeNode* root) {traverse(root);return res;}// 遍历二叉树void traverse(TreeNode* root) {if (root nullptr) {return;}// 前序遍历位置depth;// 遍历的过程中记录最大深度res max(res, depth);traverse(root-left);traverse(root-right);// 后序遍历位置depth--;}
};
solution 2 分解问题
我们要求一颗二叉树的最大深度我们只需要分别知道它的左右子树的最大深度即可然后return 1根节点maxleftmaxrightmax就行了
class Solution2 {// 定义输入一个节点返回以该节点为根的二叉树的最大深度
public:int maxDepth(TreeNode* root) {if (root nullptr) {return 0;}int leftMax maxDepth(root-left);int rightMax maxDepth(root-right);// 根据左右子树的最大深度推出原二叉树的最大深度return 1 max(leftMax, rightMax);}
};111.二叉树的最小深度 算法思路及代码
solution 1
// 「遍历」的递归思路
class Solution {
private:int minDepthValue INT_MAX;int currentDepth 0;void traverse(TreeNode* root) {if (root nullptr) {return;}// 做选择在进入节点时增加当前深度currentDepth;// 如果当前节点是叶子节点更新最小深度if (root-left nullptr root-right nullptr) {minDepthValue std::min(minDepthValue, currentDepth);}traverse(root-left);traverse(root-right);// 撤销选择在离开节点时减少当前深度currentDepth--;}public:int minDepth(TreeNode* root) {if (root nullptr) {return 0;}traverse(root);return minDepthValue;}
};
solution 2
我觉得有了上一题的铺垫首先应该是想到这种办法思路也非常明确就是想找到左右子树各自的最小深度然后再加上根节点 但是力扣给的示例没有全部通过它给的示例是一颗斜树准确的来说是条五个节点的链表这种就是极端的情况我们怎么去解决它呢 根本问题就是要防止当左子树为空时直接return 0的情况发生参照下面的预期结果所以我们就需要在即将离开一个节点之前判断此时的左右子树是否为空也就是leftmin/rightmin为0的情况 例如 leftmin0那么我们就return 1rightmin参考根节点的情况就行了 那为什么在求最大深度的时候不会出现这个问题呢 给我的感觉 是因为在求最大深度时我们的出口是到叶子节点就行一股脑的往下冲不会面临着是否为空的问题 而我们要求最小深度时其实更像是一个探险的人需要一步一步地走需要避开危险
deepseek 最小深度中当左子树为空时(root.left为None)右子树的深度决定了当前节点的最小深度。同理处理右子树为空的情况。只有左右子树均存在时才取较小值加1确保路径有效。关键 最大深度直接取左右子树的最大值加1无需特殊处理空子树因为空子树的深度0不会影响非空子树的最大值结果 修改之后AC
class Solution {
public:int minDepth(TreeNode* root) {if(rootnullptr){return 0;}int rightminminDepth(root-right);int leftminminDepth(root-left);if(leftmin0){return rightmin1;}if(rightmin0){return leftmin1;}return 1min(leftmin,rightmin);}
};222.完全二叉树的结点个数 算法思路和代码
solution 1
读完这道题我就有思路了就是把左右子树的分别有多少个节点给他算出来然后相加不就行了吗 确实能AC也很简单 但是这题特意说了是完全二叉树的节点 意味着我们其实是可以利用完全二叉树的特性来解决问题的这才是这题高效率的关键因此就有了solution2
class Solution {
public:int countNodes(TreeNode* root) {if(rootnullptr){return 0;}int leftcountNodes(root-left);int rightcountNodes(root-right);int resultleftright1;return result;}
};solution 2 假如你学习过懒猫老师的课程你一定知道如果给你一个满二叉树的深度k那么它的节点数就是2的k次方-1而给你一个二叉树的层数x那么这一层有2的X-1次幂 个节点
#include cmathclass Solution {
public:int countNodes(TreeNode* root) {TreeNode* l root;TreeNode* r root;// 记录左、右子树的高度int hl 0, hr 0;while (l ! nullptr) {l l-left;hl;}while (r ! nullptr) {r r-right;hr;}// 如果左右子树的高度相同则是一棵满二叉树if (hl hr) {return (int)pow(2, hl) - 1;}// 如果左右高度不同则按照普通二叉树的逻辑计算return 1 countNodes(root-left) countNodes(root-right);}
};110 平衡二叉树 一棵高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1
算法思路及代码
solution
对于这道题其实不用想的太复杂还是一样就问你是不是遍历一遍就可以判断是否为二叉平衡树了怎么判断呢是不是把两个左右子树高度搞出来然后比较一下就行了代码上就是借助一个外部变量然后一个compare函数就行 需要注意的是定义里提到了绝对值那么最简单能准确表达的 就是借助abs绝对值函数会用就行 我们需要知道这个compare函数帮我们做了什么事情需要明确给出这个函数的定义返回以该节点为根节点的二叉树的高度如果不是平衡二叉树了则返回-1 不然就很容易被绕进去 明确单层递归的逻辑 如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢当然是其左子树高度和其右子树高度的差值。 分别求出其左右子树的高度然后如果差值小于等于1则返回当前二叉树的高度否则返回-1表示已经不是二叉平衡树了。
class Solution {
public:int compare_height(TreeNode* root){if(rootnullptr){return 0;}int leftcompare_height(root-left);if(left-1){return -1;}int rightcompare_height(root-right);if(right-1){return -1;}return abs(left - right) 1 ? -1 : 1 max(left, right);}bool isBalanced(TreeNode* root) {int result compare_height(root);if(result!-1){return true;}else{return false;}}
};257 二叉树的所有路径 这题其实还是有一些不一样 回溯的味道非常明显了 这也是labuladong在它的文章中提到的二叉树与动态规划和回溯算法之间的关系
算法思路及代码 404 左叶子之和 算法思路与代码 solution
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(rootnullptr){return 0;}if(root-leftnullptr root-rightnullptr)//叶子节点{return 0;}int leftsumsumOfLeftLeaves(root-left);if(root-left!nullptr root-left-leftnullptr root-left-rightnullptr){leftsumroot-left-val;}int rightsumsumOfLeftLeaves(root-right);int sumleftsumrightsum;return sum;}
};513 找树左下角的值 算法思路及代码
solution1 遍历
对于这题来说 详细的过程都在代码随想录详细版
首先 思路是先用遍历的方式来解决 一个find函数和一个变量depth就能解决问题其次我们需要确定这个函数的终止条件递归的出口是不是当遇到叶子节点的时候就需要更新depth了用一个result记录此时深度最左边节点的值再次我们需要给这个find函数一个明确的定义就是给一个根节点返回最大深度最左边孩子的值细节方面 由于求得是最大深度 我们的depth是需要不断更新的 就是说我们需要一个全局变量保存depth的值 由于我们需要再往下遍历之前记录此时的深度 所以还是采用前序遍历先给MAXdepth先定义成最小的整型确保MAXdepth能够正常更新 result同理
class Solution {
public:
int MaxdepthINT_MIN;
int result;void traverse(TreeNode* root,int depth){if(root-leftnullptr root-rightnullptr){//如果找到叶子节点更新最大深度if(depthMaxdepth){Maxdepthdepth;resultroot-val;}return;}if(root-left!nullptr){depth;//前序位置traverse(root-left,depth);depth--;//后序位置 回溯在离开节点时维护depth}if(root-right!nullptr){depth;traverse(root-right,depth);depth--;}return;}int findBottomLeftValue(TreeNode* root) {traverse(root,0);return result;}solution 2迭代
我们只需要在层序遍历到最后一层时 记录最后一层的第一个节点即可 利用了CSTL容器和队列先进先出的特点 定义了一个结点类型的队列 用于存储树的节点 弄个node指向每一层的第一个节点result记录每次node指向的值直到队空停止循环
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queueTreeNode* que;if (root ! NULL) que.push(root);int result 0;while (!que.empty()) {int size que.size();for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (i 0) result node-val; // 记录最后一行第一个元素if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return result;}
};112.路径总和 算法思路以及代码
思路概述 我们需要判断二叉树中是否存在从根节点到叶子节点的路径使得路径上所有节点值的和等于给定的目标和 targetSum。我们可以通过递归的方式实现这一点具体来说使用前序遍历根-左-右来遍历二叉树。 详细步骤 定义 findPath 函数 参数 cur当前处理的节点。 sum当前路径的累加和。 targetSum目标和。 返回值布尔值表示是否存在从当前节点到叶子节点的路径路径和等于 targetSum。 检查空节点 如果当前节点 cur 为空直接返回 false因为空节点不可能构成路径。 累加节点值 将当前节点的值 cur-val 累加到路径和 sum 中。 检查叶子节点 如果当前节点是叶子节点即没有左子节点和右子节点检查路径和 sum 是否等于目标和 targetSum。 如果相等返回 true表示找到了满足条件的路径。 否则返回 false。 递归检查左子树 递归调用 findPath 处理左子树 cur-left。 如果左子树中存在满足条件的路径返回 true。 递归检查右子树 递归调用 findPath 处理右子树 cur-right。 如果右子树中存在满足条件的路径返回 true。 返回结果 如果左右子树中都没有找到满足条件的路径返回 false。
solution 1
暴力
一开始我想用一个vector向量来保存每次递归到叶子节点sum的值 也就是说需要遍历出所有路线然后在主函数中for循环遍历我们的vector 如果找到了targetsum就return true 找不到就return false
#include iostream
#include vectorusing namespace std;// 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:// 辅助函数用于递归查找路径和并存储在 record 向量中void findPath(TreeNode* cur, int sum, int targetSum, vectorint record) {// 如果当前节点为空直接返回if (cur nullptr) {return;}// 累加当前节点的值到路径和sum cur-val;// 检查当前节点是否是叶子节点即没有左子节点和右子节点if (cur-left nullptr cur-right nullptr) {// 如果是叶子节点将路径和添加到 record 向量中record.push_back(sum);return;}// 递归检查左子树findPath(cur-left, sum, targetSum, record);// 递归检查右子树findPath(cur-right, sum, targetSum, record);}// 主函数判断是否存在路径和等于目标和bool hasPathSum(TreeNode* root, int targetSum) {vectorint record; // 用于存储每条路径的和findPath(root, 0, targetSum, record); // 调用辅助函数 findPath// 遍历 record 向量检查是否存在等于 targetSum 的路径和for (int sum : record) {if (sum targetSum) {return true;}}// 如果没有找到等于 targetSum 的路径和返回 falsereturn false;}
}; 但是这个思路确实是太麻烦了是可以去优化的
class Solution {
public:// 辅助函数用于递归查找路径和bool findPath(TreeNode* cur, int sum, int targetSum) {// 如果当前节点为空直接返回 falseif (cur nullptr) {return false;}// 累加当前节点的值到路径和sum cur-val;// 检查当前节点是否是叶子节点即没有左子节点和右子节点if (cur-left nullptr cur-right nullptr) {// 如果路径和等于目标和返回 truereturn sum targetSum;}// 递归检查左子树如果左子树中存在满足条件的路径返回 trueif (findPath(cur-left, sum, targetSum)) {return true;}// 递归检查右子树如果右子树中存在满足条件的路径返回 trueif (findPath(cur-right, sum, targetSum)) {return true;}// 如果左右子树中都没有找到满足条件的路径返回 falsereturn false;}// 主函数判断是否存在路径和等于目标和bool hasPathSum(TreeNode* root, int targetSum) {// 调用辅助函数 findPath 从根节点开始查找return findPath(root, 0, targetSum);}
}; solution 2
其实跟方法一在思路上本质上是一样的
class Solution 2 {
public:// 辅助函数用于递归查找路径和bool findPath(TreeNode* cur, int sum, int targetSum) {// 如果当前节点为空直接返回 falseif (cur nullptr) {return false;}// 累加当前节点的值到路径和sum cur-val;// 检查当前节点是否是叶子节点即没有左子节点和右子节点if (cur-left nullptr cur-right nullptr) {// 如果路径和等于目标和返回 truereturn sum targetSum;}// 递归检查左子树如果左子树中存在满足条件的路径返回 trueif (findPath(cur-left, sum, targetSum)) {return true;}// 递归检查右子树如果右子树中存在满足条件的路径返回 trueif (findPath(cur-right, sum, targetSum)) {return true;}// 如果左右子树中都没有找到满足条件的路径返回 falsereturn false;}// 主函数判断是否存在路径和等于目标和bool hasPathSum(TreeNode* root, int targetSum) {// 调用辅助函数 findPath 从根节点开始查找return findPath(root, 0, targetSum);}
};
106 中序与后序遍历序列构造二叉树 我觉得一上来就做这题以及后面的同类型题目其实还是比较困难的 因为我们一开始在学习二叉树的前中后序遍历时一般都是给我们一颗二叉树 让我们给出它的前中后序的遍历序列 这是一个正向的过程 而本题刚刚好是不是完全相反了啊 所以比较难 希望大家在做这题之前去看一下懒猫老师的视频 如果不明白C STL的map以及它的基本操作 也需要去了解一下 懒猫老师-数据结构-(29)根据二叉树的遍历结果确定二叉树 如果你看完这个视频 相信你一定对于这题有了最基本的认知只不过对于代码实现还是不太清楚 也就是说 你知道给你一个前序和中序/后序遍历序列能确定唯一的二叉树 你在看后面的题目 给你一个前序后序 题目只要你返回任意一颗满足的二叉树即可 这就是原因所在 其实我觉得区别这些的关键其实就是对于每颗子树的根节点怎么去找
思路及代码
主函数是buildTree 辅助函数是build 哈希表inpos的作用就是存储中序遍历的值与其位置的映射比如说后序遍历的最后一个元素是根节点 我们现在想确定它的左右子树 那么我们只需要找到这个根节点在中序遍历上的位置即可 左边就是左子树 右边就是右子树
solution
il ir分别表示前序遍历序列的左右两端 plpr分别表示后序遍历的左右两端我用AI补全了注释方便理解 如果还有不懂的地方直接看视频就好 我附在这里 真的是讲的非常好 106. 从中序与后序遍历序列构造二叉树 | 手写图解版思路 代码讲解 // Solution类用于根据中序和后序遍历数组构建二叉树
class Solution {// 使用哈希表存储中序遍历中每个值的位置以便快速查找根节点在中序遍历中的位置unordered_mapint,intinpos;
public:/*** 主要的构建函数接收中序和后序遍历数组作为输入* param inorder 中序遍历数组* param postorder 后序遍历数组* return 返回构建的二叉树根节点*/TreeNode* buildTree(vectorint inorder, vectorint postorder) {int ninorder.size();// 遍历中序遍历数组记录每个值的位置for(int i0;in;i){inpos[inorder[i]]i;}// 调用build函数开始构建二叉树return build(inorder,postorder,0,n-1,0,n-1);}/*** 递归构建二叉树的辅助函数* param inorder 中序遍历数组* param postorder 后序遍历数组* param il 中序遍历的左边界* param ir 中序遍历的右边界* param pl 后序遍历的左边界* param pr 后序遍历的右边界* return 返回当前递归构建的子树根节点*/TreeNode* build(vectorint inorder,vectorint postorder,int il,int ir,int pl,int pr){// 如果中序遍历的左边界大于右边界说明已经没有节点返回空指针if(ilir || plpr){return nullptr;}// 计算左子树的节点个数int kinpos[postorder[pr]]-il;// 获取当前子树的根节点值int rootvalpostorder[pr];// 创建根节点TreeNode* root new TreeNode(rootval);// 递归构建左子树root-leftbuild(inorder,postorder,il,ilk-1,pl,plk-1);// 递归构建右子树root-rightbuild(inorder,postorder,ilk1,ir,plk,pr-1);// 返回构建的根节点return root;}
};
相关题目
前序中序
TreeNode* constructMaximumBinaryTree([3,2,1,6,0,5]) {// 找到数组中的最大值TreeNode* root new TreeNode(6);// 递归调用构造左右子树root-left constructMaximumBinaryTree({3,2,1});root-right constructMaximumBinaryTree({0,5});return root;
}// 当前 nums 中的最大值就是根节点然后根据索引递归调用左右数组构造左右子树即可
// 再详细一点就是如下伪码
TreeNode* constructMaximumBinaryTree(vectorint nums) {if (nums.empty()) return nullptr;// 找到数组中的最大值int maxVal INT_MIN;int index 0;for (int i 0; i nums.size(); i) {if (nums[i] maxVal) {maxVal nums[i];index i;}}TreeNode* root new TreeNode(maxVal);// 递归调用构造左右子树root-left constructMaximumBinaryTree(nums[0..index-1]);root-right constructMaximumBinaryTree(nums[index1..nums.size()-1]);
}前序后序不唯一
class Solution {// 存储 postorder 中值到索引的映射unordered_mapint, int valToIndex;public:TreeNode* constructFromPrePost(vectorint preorder, vectorint postorder) {for (int i 0; i postorder.size(); i) {valToIndex[postorder[i]] i;}return build(preorder, 0, preorder.size() - 1,postorder, 0, postorder.size() - 1);}// 定义根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd]// 构建二叉树并返回根节点。TreeNode* build(vectorint preorder, int preStart, int preEnd,vectorint postorder, int postStart, int postEnd) {if (preStart preEnd) {return nullptr;}if (preStart preEnd) {return new TreeNode(preorder[preStart]);}// root 节点对应的值就是前序遍历数组的第一个元素int rootVal preorder[preStart];// root.left 的值是前序遍历第二个元素// 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点// 确定 preorder 和 postorder 中左右子树的元素区间int leftRootVal preorder[preStart 1];// leftRootVal 在后序遍历数组中的索引int index valToIndex[leftRootVal];// 左子树的元素个数int leftSize index - postStart 1;// 先构造出当前根节点TreeNode* root new TreeNode(rootVal);// 递归构造左右子树// 根据左子树的根节点索引和元素个数推导左右子树的索引边界root-left build(preorder, preStart 1, preStart leftSize,postorder, postStart, index);root-right build(preorder, preStart leftSize 1, preEnd,postorder, index 1, postEnd - 1);return root;}
};654 最大二叉树 思路及代码
*每个二叉树节点都可以认为是一棵子树的根节点对于根节点首先要做的当然是把想办法把自己先构造出来然后想办法构造自己的左右子树。
所以我们要遍历数组把找到最大值 maxVal从而把根节点 root 做出来然后对 maxVal 左边的数组和右边的数组进行递归构建作为 root 的左右子树。*
solution
class Solution1 {
public:TreeNode* constructMaximumBinaryTree(vectorint nums) {//递归终止条件只有一个元素的时候if(nums.size()1)return new TreeNode (nums[0]);//我们需要记录最大值来输出 以及索引下标来分隔左子树 右子树int maxval0;int index0;//遍历整个数组找到最大值for(int i0;inums.size();i){if(nums[i]maxval){maxvalnums[i];indexi;//不断更新maxval//直到遍历完整个数组找到最大值}}TreeNode* rootnew TreeNode(maxval);//递归创建左子树if(index0){vectorintvec(nums.begin(),nums.begin()index) ;//创建一个数组来存储左子树元素范围root-leftconstructMaximumBinaryTree(vec);}//右子树if(indexnums.size()-1)//说明至少还有一个元素{vectorintvec2(nums.begin()index1,nums.end());root-rightconstructMaximumBinaryTree(vec2);}return root;}
};
**************************************
class Solution2 {
public:// 主函数TreeNode* constructMaximumBinaryTree(std::vectorint nums) {return build(nums, 0, nums.size() - 1);}// 定义将 nums[lo..hi] 构造成符合条件的树返回根节点TreeNode* build(std::vectorint nums, int lo, int hi) {// base caseif (lo hi) {return nullptr;}// 找到数组中的最大值和对应的索引int index -1, maxVal INT_MIN;for (int i lo; i hi; i) {if (maxVal nums[i]) {index i;maxVal nums[i];}}TreeNode* root new TreeNode(maxVal);// 递归调用构造左右子树root-left build(nums, lo, index - 1);root-right build(nums, index 1, hi);return root;}
};二叉搜索树相关
700.二叉搜索树中的搜索 算法思路与代码
就是利用二叉搜索树左根右的特性 使得我们不用去搜索整颗二叉树去找到target
solution
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(rootnullptr || root-valval){return root;} if(root-valval){return searchBST(root-left,val);}if(root-valval){return searchBST(root-right,val);}return nullptr;}
};
