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

外国人学做中国菜的网站源码论坛网站

外国人学做中国菜的网站,源码论坛网站,社区服务呼叫系统 网站的建设,WordPress文章批量生成器二叉树的深搜 验证二叉搜索树 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下: 节点的左 子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉…

二叉树的深搜

在这里插入图片描述

验证二叉搜索树

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左

    子树

    只包含

    小于

    当前节点的数。

  • 节点的右子树只包含 大于 当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

在这里插入图片描述

输入:root = [2,1,3]
输出:true

示例 2:

在这里插入图片描述

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。

在这里插入图片描述

提示:

  • 树中节点数目范围在[1, 104]
  • -231 <= Node.val <= 231 - 1

解法(利⽤中序遍历):

后序遍历按照左⼦树、根节点、右⼦树的顺序遍历⼆叉树的所有节点,通常⽤于⼆叉搜索树相关题 ⽬。

算法思路:

如果⼀棵树是⼆叉搜索树,那么它的中序遍历的结果⼀定是⼀个严格递增的序列。 因此,我们可以初始化⼀个⽆穷⼩的全区变量,⽤来记录中序遍历过程中的前驱结点。那么就可以在 中序遍历的过程中,先判断是否和前驱结点构成递增序列,然后修改前驱结点为当前结点,传⼊下⼀ 层的递归中。

算法流程:

  1. 初始化⼀个全局的变量prev,⽤来记录中序遍历过程中的前驱结点的val;

  2. 中序遍历的递归函数中:

a. 设置递归出⼝:root==nullptr的时候,返回true;

b. 先递归判断左⼦树是否是⼆叉搜索树,⽤retleft标记;

c. 然后判断当前结点是否满⾜⼆叉搜索树的性质,⽤retcur标记:

▪ 如果当前结点的val⼤于prev,说明满⾜条件,retcur改为true;

▪ 如果当前结点的val⼩于等于prev,说明不满⾜条件,retcur改为false;

d. 最后递归判断右⼦树是否是⼆叉搜索树,⽤retright标记;

  1. 只有当retleft、retcur和retright都是true的时候,才返回true。

代码如下:

/*** 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 
{long prev = LONG_MIN;public:bool isValidBST(TreeNode* root) 
{if(root == nullptr) return true;bool left = isValidBST(root->left);// 剪枝if(left == false) return false;bool cur = false;if(root->val > prev)cur = true;// 剪枝if(cur == false) return false;prev = root->val;bool right = isValidBST(root->right);return left && right && cur;}};

二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 小的元素(从 1 开始计数)。

示例 1:

在这里插入图片描述

输入:root = [3,1,4,null,2], k = 1
输出:1

示例 2:

在这里插入图片描述

输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3

提示:

  • 树中的节点数为 n
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104

解法⼆(中序遍历+计数器剪枝):

算法思路:

上述解法不仅使⽤⼤量额外空间存储数据,并且会将所有的结点都遍历⼀遍。

但是,我们可以根据中序遍历的过程,只需扫描前k个结点即可。

因此,我们可以创建⼀个全局的计数器count,将其初始化为k,每遍历⼀个节点就将count–。直到 某次递归的时候,count的值等于1,说明此时的结点就是我们要找的结果。

算法流程:

  1. 定义⼀个全局的变量count,在主函数中初始化为k的值(不⽤全局也可以,当成参数传⼊递归过 程中);

递归函数的设计:int dfs(TreeNode * root):

• 返回值为第k个结点;

递归函数流程(中序遍历):

  1. 递归出⼝:空节点直接返回-1,说明没有找到;

  2. 去左⼦树上查找结果,记为retleft:

    a. 如果retleft==-1,说明没找到,继续执⾏下⾯逻辑;

    b. 如果retleft!=-1,说明找到了,直接返回结果,⽆需执⾏下⾯代码(剪枝);

    1. 如果左⼦树没找到,判断当前结点是否符合:

      a. 如果符合,直接返回结果

      1. 如果当前结点不符合,去右⼦树上寻找结果。

在这里插入图片描述

代码如下:

/*** 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 count=0;int ret=0;int kthSmallest(TreeNode* root, int k) {count=k;dfs(root);return ret;}void dfs(TreeNode*root){if(root==nullptr||count==0) return;dfs(root->left);count--;if(count==0)  ret=root->val;dfs(root->right);}
};

二叉树的所有路径

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1:

在这里插入图片描述

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]

示例 2:

输入:root = [1]
输出:["1"]

提示:

  • 树中节点的数目在范围 [1, 100]
  • -100 <= Node.val <= 100

在这里插入图片描述

解法(回溯):

算法思路:

使⽤深度优先遍历(DFS)求解。

路径以字符串形式存储,从根节点开始遍历,每次遍历时将当前节点的值加⼊到路径中,如果该节点 为叶⼦节点,将路径存储到结果中。否则,将"->"加⼊到路径中并递归遍历该节点的左右⼦树。 定义⼀个结果数组,进⾏递归。

递归具体实现⽅法如下:

  1. 如果当前节点不为空,就将当前节点的值加⼊路径path中,否则直接返回;

  2. 判断当前节点是否为叶⼦节点,如果是,则将当前路径加⼊到所有路径的存储数组paths中;

  3. 否则,将当前节点值加上"->"作为路径的分隔符,继续递归遍历当前节点的左右⼦节点。

  4. 返回结果数组。

    • 特别地,我们可以只使⽤⼀个字符串存储每个状态的字符串,在递归回溯的过程中,需要将路径中 的当前节点移除,以回到上⼀个节点。

    具体实现⽅法如下:

    1. 定义⼀个结果数组和⼀个路径数组。

    2. 从根节点开始递归,递归函数的参数为当前节点、结果数组和路径数组。

      a. 如果当前节点为空,返回。

      b. 将当前节点的值加⼊到路径数组中。

      c. 如果当前节点为叶⼦节点,将路径数组中的所有元素拼接成字符串,并将该字符串存储到结果 数组中。

      d. 递归遍历当前节点的左⼦树。

      e. 递归遍历当前节点的右⼦树。

      f. 回溯,将路径数组中的最后⼀个元素移除,以返回到上⼀个节点。

      1. 返回结果数组。

代码如下:

/*** 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:vector<string> ret;vector<string> binaryTreePaths(TreeNode* root) {string path;if(root==nullptr) return ret;dfs(root,path);return ret;}void dfs(TreeNode*root,string path){path+=to_string(root->val);if(root->left==nullptr&&root->right==nullptr){ret.push_back(path);return ;}path+="->";if(root->left)  dfs(root->left,path);if(root->right)  dfs(root->right,path);}
};
http://www.yayakq.cn/news/316358/

相关文章:

  • 山西建设局网站wordpress安装怎么切换中文
  • 自己怎么做网站的聚合页面国外服务器公司有哪些
  • 做网站排名费用多少上海专业的网站
  • 爱心互助网站开发前端网站开发上线的流程
  • 湖南网站建设网络公司沈阳建信建设工程有限公司
  • 北京邢台企业商会网站莱芜民生网站
  • 山西太原网站建设公司打开浏览器自动弹出2345网址导航
  • 雅虎网站收录提交入口mil后缀网站
  • 页游平台网站网站网页文案怎么写
  • 建设银行深分行圳招聘网站建设网站怎样挣钱
  • 广州网站建站平台网站推广方案的构成
  • 如何维护自己公司的网站南阳商都网站做网站
  • 图片网站如何优化专门做任务的网站
  • 动态视频网站开发各大网站的网址
  • 网站为什么上传不了图片做招聘和求职都需要哪些网站
  • html语言做网站网站发语音功能如何做
  • 网站国内空间和国外空间主体负责人和网站负责人不能是同一个人
  • 镇江市住房与城乡建设部网站网站建设 保密
  • 北京宏福建设有限公司网站山东做公司网站
  • 网站设计动画宝客上海网络科技有限公司
  • 12306网站是谁做的做名人故居的网站多少钱
  • 用wordpress建站之后如何优化深圳做个网站要多少钱
  • 住房和城乡建设部注册中心网站营销网站建设选择原则
  • 制作好的网站产品推广的目的和意义
  • 佛山三水网站建设wordpress建立商城
  • 广州哪个公司做网站好淘宝店有给网站做优化am
  • 网站开发实训做的网站在百度找不到
  • 怎么在建设银行网站购买国债wordpress 图片选择器
  • 推广类网站wordpress4.4.2下载
  • 网站后台logo深圳手机网站建设服务