我要招人

去企业版

首页 > 试题广场 >

找到搜索二叉树中两个错误的节点

[编程题]找到搜索二叉树中两个错误的节点

热度指数：15138 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)

搜索二叉树：满足每个节点的左子节点小于当前节点，右子节点大于当前节点。

样例1图

样例2图

数据范围： $3 \le n \le 100000$ ,节点上的值满足 $1 \le val \le n$ ，保证每个value各不相同

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3}

输出

[1,2]

说明

如题面图

示例2

输入

{4,2,5,3,1}

输出

[1,3]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

堆栈哲学

发表于 2021-07-14 22:54:35

精华题解题意分析：在做这道题之前，最好是先了解什么是搜索二叉树(BST) 左子树的值小于根节点右子树的值大于根节点子树同样满足上述规则 BST: 可以参考图解示例：解法一：递归因为二叉搜索树的中序遍历是正序数组，所以直接进行中序遍历，遍历的过程中直接找出异常值分析结果可得。展开全文

Maokt

发表于 2021-07-14 10:19:32

精华题解算法思想一：中序遍历+数组解题思路：先求出中序遍历，然后根据中序遍历的结果求出异常值 1. 先用中序遍历遍历树，得到一个部分排序数组，该数组中有两个数交换了位置，现在的问题变成了从一个部分有序的数组中找出交换了位置的那两个数 2. 因为此时的情况必定是一个小的数放到了后面，一个展开全文

SandMonth

发表于 2021-07-16 18:05:28

精华题解找到搜索二叉树中的两个错误结点一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同) 输入：{1,2,3}返回值：[1,2] 方法一中序遍历首先先了解一下搜索二叉树的性质: 如果该树的左子树展开全文

2019113913

发表于 2021-07-14 17:32:31

精华题解题意思路：一棵二叉搜索树其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同）。方法一:中序遍历二叉树先用中序遍历遍历二叉搜索树。中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则：（1）中序遍历展开全文

失败的cc

发表于 2020-12-16 12:31:12

// public class TreeNode { // int val = 0; // TreeNode left = null; // TreeNode right = null; // } // 1. 先求出中序遍历，然后根据中序遍历的结果求出异常值 import 展开全文

摸鱼学大师

发表于 2021-12-07 19:35:03

题目的主要信息：一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值该二叉树每个节点值不同方法一：中序非递归具体做法：使用栈辅助进行二叉树的中序遍历：栈记录当前节点，不断往左深入，直到左边子树为空，再弹出栈顶（即为当前展开全文

小陆要懂云

发表于 2021-09-04 16:12:52

利用迭代式中序遍历，找到两个错误的节点。以中序遍历序列【1，2，6，4，5，3】为例，其两个错误的节点是6和3，那么只有当遍历到4时，才能发现6是错误的节点，因此用x存储4的上一个节点，也就是6；当遍历到第二个错误节点的时候，可以直接发现3小于5，用y存储当前节点就好。 vector& 展开全文

靓女语塞........

发表于 2020-10-18 10:33:12

class Solution {public://中序遍历搜索二叉树按递增顺序，除了两个错误节点 //记录错误节点a,b int a=0; int b=0; TreeNode* pre=nullptr; void inorder(TreeNode* root){ 展开全文

牛客451787383号

发表于 2024-06-08 22:25:51

# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿展开全文

coder6458

发表于 2022-06-30 18:08:33

class Solution { public: /** * * @param root TreeNode类 the root * @ret 展开全文

觉醒火龙果很想五点下课

发表于 2025-06-30 18:32:34

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) { 展开全文