recover-binary-search-tree

2024-05-02 02:48
文章标签 tree search binary recover

本文主要是介绍recover-binary-search-tree,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、链接:recover-binary-search-tree
来源:牛客网

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note: 
A solution using O(n ) space is pretty straight forward. Could you devise a constant space solution?confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:1/ \2   3/4\5
The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

2、思路:二叉搜索树是否出现错误结点可以转换为中序遍历的前一个元素是否一直小于当前元素。总共分为下面两种情况:

  • {0,1}
  • {2,3,1}
    如果出现前一个结点大于当前结点,将其记录下来即可。
    3、代码:
public class RecoverSearchTree {public static void main(String[] args) {TreeNode root =new TreeNode(0);root.left = new TreeNode(1);RecoverSearchTree test = new RecoverSearchTree();test.recoverTree(root);}private TreeNode firstErrorNode = null;private TreeNode secondErrorNode = null;private TreeNode preNode = new TreeNode(Integer.MIN_VALUE);public void recoverTree(TreeNode root) {inOrder(root);int temp = firstErrorNode.val;firstErrorNode.val = secondErrorNode.val;secondErrorNode.val = temp;}private void inOrder(TreeNode root) {if(root == null)return;inOrder(root.left);if(preNode.val >= root.val ){if(firstErrorNode == null){firstErrorNode = preNode;secondErrorNode = root;}else{secondErrorNode = root;}}//为什么这样可以记录上一个元素//因为打印的话是中序遍历的顺序,如果当前执行第一次preNode保存root//第二次执行到这句时就是当前root的上一个元素了preNode = root;inOrder(root.right);}
}

这篇关于recover-binary-search-tree的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/953244

相关文章

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

树(Tree)——《啊哈!算法》

树 什么是树?树是一种特殊的图,不包含回路的连通无向树。 正因为树有着“不包含回路”这个特点,所以树就被赋予了很多特性。 一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点,那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。 一棵树有且只有一个根结点。 没有父结点的结点称为根结点(祖先)。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶

JavaScript正则表达式六大利器:`test`、`exec`、`match`、`matchAll`、`search`与`replace`详解及对比

在JavaScript中,正则表达式(Regular Expression)是一种用于文本搜索、替换、匹配和验证的强大工具。本文将深入解析与正则表达式相关的几个主要执行方法:test、exec、match、matchAll、search和replace,并对它们进行对比,帮助开发者更好地理解这些方法的使用场景和差异。 正则表达式基础 在深入解析方法之前,先简要回顾一下正则表达式的基础知识。正则

插件maven-search:Maven导入依赖时,使用插件maven-search拷贝需要的依赖的GAV

然后粘贴: <dependency>    <groupId>mysql</groupId>    <artifactId>mysql-connector-java</artifactId>    <version>8.0.26</version> </dependency>

226 Invert Binary Tree

//226 Invert Binary Tree//算法思路:主要使用递归算法public class Solution {public TreeNode invertTree(TreeNode root) {//1 出口 空节点if (root==null)return null;//2 递归 调用自己TreeNode left = root.left;TreeNode right = ro

广度优先搜索Breadth-First-Search

目录  1.问题 2.算法 3.代码 4.参考文献  1.问题         广度优先搜索,稍微学过算法的人都知道,网上也一大堆资料,这里就不做过多介绍了。直接看问题,还是从下图招到一条从城市Arad到Bucharest的路径。  该图是连通图,所以必然存在一条路径,只是如何找到最短路径。 2.算法 还是贴一个算法的伪代码吧: 1 procedu

【0323】Postgres内核之 hash table sequentially search(seq_scan_tables、num_seq_scans)

0. seq scan tracking 我们在这里跟踪活跃的 hash_seq_search() 扫描。 需要这种机制是因为如果扫描正在进行时发生桶分裂(bucket split),它可能会访问两次相同的条目,甚至完全错过某些条目(如果它正在访问同一个分裂的桶中的条目)。因此,如果正在向表中插入数据,我们希望抑制桶分裂。 在当前的使用中,这种情况非常罕见,因此只需将分裂推迟到下一次插入即可。

Sorry!Hbase的LSM Tree就是可以为所欲为!

我们先抛出一个问题: LSM树是HBase里使用的非常有创意的一种数据结构。在有代表性的关系型数据库如MySQL、SQL Server、Oracle中,数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中,则是使用日志结构合并树(Log-structured Merge Tree,LSM Tr

【spring】does not have member field ‘com.sun.tools.javac.tree.JCTree qualid

spring-in-action-6-samples 的JDK版本 最小是11,我使用 了22: jdk21 jdk22 都与lombok 不兼容,必须使用兼容版本, 否则报错: thingsboard 的大神解释了: java: java.lang.NoSuchFieldError: Class com