首页 > 试题广场 >

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

[编程题]找到搜索二叉树中两个错误的节点
  • 热度指数：14817 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)
搜索二叉树：满足每个节点的左子节点小于当前节点，右子节点大于当前节点。
样例1图

样例2图

数据范围：,节点上的值满足 ，保证每个value各不相同
进阶：空间复杂度 ，时间复杂度
示例1

输入

{1,2,3}

输出

[1,2]

说明

如题面图
示例2

输入

{4,2,5,3,1}

输出

[1,3]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
开通博客
头像 堆栈哲学
发表于 2021-07-14 22:54:35
精华题解 题意分析： 在做这道题之前，最好是先了解什么是搜索二叉树(BST) 左子树的值小于根节点 右子树的值大于根节点 子树同样满足上述规则 BST: 可以参考图解示例： 解法一：递归 因为二叉搜索树的中序遍历是正序数组，所以直接进行中序遍历，遍历的过程中直接找出异常值分析结果可得。 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 Maokt
发表于 2021-07-14 10:19:32
精华题解 算法思想一：中序遍历+数组 解题思路： 先求出中序遍历，然后根据中序遍历的结果求出异常值 1. 先用中序遍历遍历树，得到一个部分排序数组，该数组中有两个数交换了位置，现在的问题变成了从一个部分有序的数组中找出交换了位置的那两个数 2. 因为此时的情况必定是一个小的数放到了后面，一个 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 SandMonth
发表于 2021-07-16 18:05:28
精华题解 找到搜索二叉树中的两个错误结点 一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同) 输入：{1,2,3}返回值：[1,2] 方法一 中序遍历 首先先了解一下搜索二叉树的性质: 如果该树的左子树 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 2019113913
发表于 2021-07-14 17:32:31
精华题解 题意思路： 一棵二叉搜索树其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同）。 方法一:中序遍历二叉树 先用中序遍历遍历二叉搜索树。 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则： （1）中序遍历 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 失败的cc
发表于 2020-12-16 12:31:12
// public class TreeNode { // int val = 0; // TreeNode left = null; // TreeNode right = null; // } // 1. 先求出中序遍历，然后根据中序遍历的结果求出异常值 import 展开全文
去ta的博客 赞 (17) 回复(1) 收起
头像 摸鱼学大师
发表于 2021-12-07 19:35:03
题目的主要信息： 一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值 该二叉树每个节点值不同 方法一：中序非递归 具体做法： 使用栈辅助进行二叉树的中序遍历：栈记录当前节点，不断往左深入，直到左边子树为空，再弹出栈顶（即为当前 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 小陆要懂云
发表于 2021-09-04 16:12:52
利用迭代式中序遍历，找到两个错误的节点。 以中序遍历序列【1，2，6，4，5，3】为例，其两个错误的节点是6和3， 那么只有当遍历到4时，才能发现6是错误的节点，因此用x存储4的上一个节点，也就是6； 当遍历到第二个错误节点的时候，可以直接发现3小于5，用y存储当前节点就好。 vector& 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 靓女语塞........
发表于 2020-10-18 10:33:12
class Solution {public://中序遍历搜索二叉树按递增顺序，除了两个错误节点 //记录错误节点a,b int a=0; int b=0; TreeNode* pre=nullptr; void inorder(TreeNode* root){ 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 牛客451787383号
发表于 2024-06-08 22:25:51
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 coder6458
发表于 2022-06-30 18:08:33
class Solution { public:     /**      *       * @param root TreeNode类 the root      * @ret 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 杨小白~~
发表于 2022-08-01 22:49:58
func findError( root *TreeNode ) []int {     // write code here    &nb 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 前端offer收割机
发表于 2024-11-06 15:40:24
/* * function TreeNode(x) { * this.val = x; * this.left = null; * this.right = null; * } */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 苦苦_
发表于 2024-02-29 10:19:18
from pickle import NONE # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 hlh要offer
发表于 2021-08-20 15:40:08
题目 解法：中序遍历，保存上一个节点的值，如果上一个节点值大于当前节点值，保存上一个节点的值，同时保存最后一个上一个节点大于当前节点值下的当前节点值，作为结果输出 时间复杂度O(n)，空间复杂度O(1) /** * struct TreeNode { * int val; * s 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树 dfs
难度：
46条回答 5713浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号