算法通关村第九关——中序遍历与搜索树

这篇具有很好参考价值的文章主要介绍了算法通关村第九关——中序遍历与搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1 中序遍历和搜索树原理

二叉搜索树按照中序遍历正好是一个递增序列。其比较规范的定义是:

  • 若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值;
  • 若它的右子树不为空,则右子树所有节点的值均大于它的根节点的值;
  • 它的左、右子树也分别为二叉搜索树,比如下面的例子:

算法通关村第九关——中序遍历与搜索树,算法,算法,二叉搜索树,中序遍历,javascript,前端

这两棵树的中序遍历分别是[1, 2, 3, 4, 5, 6, 7, 8, 9][6, 7, 8, 9],都是二叉搜索树。

2 二叉搜索树中搜索特定值

力扣700题,给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

比如target为3,给定二叉搜索树:

			5
		   /  \
		  3    4
		 / \
         1   2

应该返回如下子树:

		  3  
		 / \
         1   2

2.1 递归实现

使用递归来实现,先来分析一下有哪些情况:

  • 如果根节点root === null或者root.val === target就直接返回根节点;
  • 如果target < root.val,说明比右子树的值小,去根节点的左子树进行查找searchBST(root.left, target);
  • 如果target > root.val,说明比左子树的值大,去根节点的右子树进行查找searchBST(root.right, target)

递归完整代码如下:

// 递归法
function searchBST(root, target) {
	// 如果根节点为空或者root.val === target,直接返回root
	if (root === null || root.val === target) {
		return root;
	}
	// 如果target < root.val,进入根节点的左子树查找
	// 如果target > root.val,进入根节点的右子树查找
	return target < root.val ? searchBST(root.left, target) : searchBST(root.right, target);
}

2.2 迭代实现

迭代逻辑:

  • 如果根节点root === null或者root.val !== target,进入下面的判断
    • 如果target < root.val,说明比右子树的值小,去根节点的左子树进行查找,root = root.left;
    • 如果target > root.val,说明比左子树的值大,去根节点的右子树进行查找,root = root.right

迭代完整代码如下:

// 迭代法
function searchBST(root, target) {
	// 如果根节点为空或者target !== root.val
	while (root !==null && target !== root.val) {
		// 如果target < root.val,进入根节点的左子树查找,root = root.left
		// 如果target > root.val,进入根节点的右子树查找,root = root.right
		root = (target < root.val ? root.left : root.right);
	}
	return root;
}

3 验证二叉搜索树

力扣98题,给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。有效二叉树定义如下:

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

分析:根据题目以及中序遍历的特性,可以知道二叉搜索树中序遍历得到的序列是一个升序序列,要判断是否是一个有效二叉树,只需要在中序遍历的时候一边遍历一边检查当前节点的值是否大于前一个遍历到的节点值即可。

3.1 递归实现

递归实现,代码如下:

function isValidBST(root) {
	let pre = Number.MIN_SAFE_INTEGER;
	return validBST(root);

	function validBST(node) {
		if (node === null) {
			return true;
		}
		// 如果左子树某个元素不满足要求就退出
		if (!validBST(node.left)) {
			return false;
		}
		// 如果当前节点值≤中序遍历前一个节点的值,不能满足二叉搜索树条件
		if (node.val <= pre) {
			return false;
		}
		pre = node.val;
		return validBST(node.right);
	}
}

3.2 迭代实现

测试用例的最小节点有可能是javascript中的最小值,因此初始化preVal = -Infinity文章来源地址https://www.toymoban.com/news/detail-666717.html

function isValidBST(root) {
	const nodeStack= [];
	let preVal = -Infinity;

	while (nodeStack.length !== 0 || root !== null) {
		while (root !== null) {
			nodeStack.push(root);
			// 先遍历左子树
			root = root.left;
		}
		// 比较左子树中间根节点与前一个节点的值,如果小与前一个节点值,说明不是二叉搜索树
		root = nodeStack.pop();
		if (root.val <= preVal) {
			return false;
		}
		preVal = root.val;
		// 再遍历右子树
		root = root.right;
	}
	return true;
}

到了这里,关于算法通关村第九关——中序遍历与搜索树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉树的遍历(先序遍历,中序遍历,后序遍历)递归与非递归算法

    先序遍历:先遍历一颗树的根节点,后遍历左子树,最后遍历右子树     先序遍历序列: 1 - 2 - 4 - 5 - 3 - 6 - 7 分解子问题方法 思路:将一颗二叉树看做两个部分,一个部分是左路节点,另一个部分是左路节点的右子树,先将二叉树的左路节点全部入栈,再依次出栈,出栈的

    2024年02月14日
    浏览(37)
  • 【算法训练-二叉树 一】【遍历二叉树】前序遍历、中序遍历、后续遍历、层序遍历、锯齿形层序遍历、二叉树右视图

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【二叉树的遍历】,使用【二叉树】这个基本的数据结构来实现,这个高频题的站点是: CodeTop ,筛选条件为: 目标公司+最近一年+出现频率排序 ,由高到低的去 牛客TOP101 去找,只有两

    2024年02月07日
    浏览(41)
  • 二叉树中序遍历非递归算法C语言实现

    // //  Inordertraverse.c //  二叉树链式存储 // //  Created by 丘** on 2021/7/28. // #include \\\"Inordertraverse.h\\\" #include stdbool.h #includestdlib.h typedef   struct StackNode {     int data;     struct StackNode* next;      }StackNode; typedef struct BiTNode {     int data;     struct BiTNode* lchild,* rchild;           }BiTnode

    2024年02月02日
    浏览(36)
  • 二叉树先序,中序,后序遍历的非递归算法(一)

    思路: 二叉树的前序遍历过程: 从树根开始沿着左子树一直深入,直到最左端无法深入时,返回; 进入最近深入时遇到结点的右子树,再进行如此的深入和返回; 直到最后从根节点的右子树返回到根节点为止; 由其深入返回的过程我们知道可以用一个栈来帮助我们消除递

    2023年04月14日
    浏览(78)
  • 算法leetcode|94. 二叉树的中序遍历(多语言实现)

    给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 树中节点数目在范围 [0, 100] 内 -100 = Node.val = 100 面对这道算法题目,二当家的再次陷入了沉思。 二叉树的中序遍历和前序遍历,后续遍历是二叉树常用的遍历方式。 使用递归方式比循环非递归方式更加简单,直观,易于

    2024年02月04日
    浏览(42)
  • 算法D14 | 二叉树1 | 144. 二叉树的前序遍历 145. 二叉树的后序遍历 94. 二叉树的中序遍历

    理论基础  需要了解 二叉树的种类,存储方式,遍历方式 以及二叉树的定义  文章讲解: 二叉树既可以链式存储(利用指针,类似栈和队列),也可以用数组表示。 深度优先遍历 前序遍历(递归法,迭代法) 中序遍历(递归法,迭代法) 后序遍历(递归法,迭代法)

    2024年02月20日
    浏览(38)
  • 算法通关村第十九关——最小路径和

    LeetCode64. 给定一个包含非负整数的 m × n 网格 grid,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 输入:grid=[[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径1→3→1→1→1的总和最小。 对于每一块方块来说,只能从他的上边或者左边走过来,所以在for循环中

    2024年02月09日
    浏览(43)
  • 算法刷题Day14 二叉树的前序、中序、后序遍历(递归、迭代、统一迭代方法)

    二叉树的定义 递归 迭代 普通的遍历(包括前序,中序和后续)迭代方法都需要借助到栈 统一迭代 统一迭代使用标记法,在栈中要处理的结点压入空指针 递归 迭代 中序遍历的迭代方法稍微特殊一点 中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问

    2024年02月15日
    浏览(46)
  • 算法练习第13天|递归实现 144.二叉树的前序遍历(opens new window)145.二叉树的后序遍历(opens new window)94.二叉树的中序遍历

    二叉树的存储方式:链式存储和顺序存储。链式存储用指针,顺序存储用数组。其结构如下图所示。 链式存储: 顺序存储: 顺序存储时,若父节点下表为i,则其左孩子下标为 2*i + 1,右孩子下标为2*i + 2. 二叉树主要有两种遍历方式: 深度优先遍历:先往深走,遇到叶子节点

    2024年02月22日
    浏览(51)
  • 编程导航算法村第九关 | 二分查找

    LeetCode852.这个题的要求有点啰嗦,核心意思就是在数组中的某位位置i开始,从0到i是递增的,从i+1 到数组最后是递减的,让你找到这个最高点。 详细要求是:符合下列属性的数组 arr 称为山脉数组 :arr.length = 3存在 i(0 i arr.length - 1)使得: ● arr[0] arr[1] … arr[i-1] arr[i] ●

    2024年02月14日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包