一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)
搜索二叉树：满足每个节点的左子节点小于当前节点，右子节点大于当前节点。
样例1图
样例2图
数据范围：
,节点上的值满足 
，保证每个value各不相同
进阶：空间复杂度 )
，时间复杂度 )
[编程题]找到搜索二叉树中两个错误的节点
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return int整型vector
*/
vector<int> findError(TreeNode* root) {
vector<int> nums; //存放中序遍历的结果
Inorder(root,nums);
vector<int> copy=nums;
sort(copy.begin(),copy.end());
vector<int> res;
int len=copy.size();
for(int i=0;i<len;++i) {
if(copy[i]!=nums[i]) {
res.push_back(copy[i]);
if(res.size()==2)
break;
}
}
return res;
}
void Inorder(TreeNode* root, vector<int>& nums) {
if(root==nullptr)
return ;
Inorder(root->left, nums);
nums.push_back(root->val);
Inorder(root->right, nums);
}
};
发表于 2021-09-23 17:28:12
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
int[] result = new int[2]; // 找到的目标节点
int findCount = 0; // 找到目标节点的数量，总数为2
int pre = 0; // 前继节点值
boolean hasPre = false; // 中序遍历是否有前继节点
// 有时候函数太多的时候就将其作为全局变量，或者有些递归函数需要的是变量值的实时情况，这个时候也需要全局变量。
// 想法：中序遍历整个树，然后找到两个降序对，第一个降序对的第一个节点值是较大数，第二个降序对的第二个节点值是较小数
public int[] findError (TreeNode root) {
// write code here
if (root.left == null && root.right == null) {
return new int[]{};
}
inorder(root);
return result;
}
private void inorder(TreeNode node) {
if (node != null && findCount != 2) {
if (node.left != null) {
inorder(node.left);
}
if (hasPre) {
if (pre > node.val) {
if (findCount == 0) {
result[1] = pre;
findCount++;
} else {
result[0] = node.val;
findCount++;
}
}
}
pre = node.val;
hasPre = true;
if (node.right != null) {
inorder(node.right);
}
}
}
}
编辑于 2021-05-22 13:40:32
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类 the root
* @return int整型一维数组
*/
public int[] findError (TreeNode root) {
TreeNode first = null, last = null;
TreeNode tail = null, pre = null, cur = root;
while (cur != null) {
tail = cur.left;
if (tail != null) {
while (tail.right != null && tail.right != cur) {
tail = tail.right;
}
if (tail.right == null) {
tail.right = cur;
cur = cur.left;
continue;
} else {
tail.right = null;
}
}
if (pre != null && pre.val > cur.val) {
last = cur;
if (first == null) {
first = pre;
}
}
pre = cur;
cur = cur.right;
}
return new int[] {last.val, first.val};
}
} morris算法实现空间复杂度O(1)
发表于 2020-08-11 21:38:07
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
/**
* NC58 找到搜索二叉树中两个错误的节点
* @author d3y1
*/
public class Solution {
private int[] result = new int[2];
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类 the root
* @return int整型一维数组
*/
public int[] findError (TreeNode root) {
// return solution1(root);
return solution2(root);
}
private int seq = 1;
private int[] solution1(TreeNode root){
inorder(root);
return result;
}
/**
* 中序遍历
* @param root
*/
private void inorder(TreeNode root){
if(root == null){
return;
}
inorder(root.left);
if(root.val != seq){
result[0] = root.val;
result[1] = seq;
}
seq++;
inorder(root.right);
}
/////////////////////////////////////////////////////////////////////////////////////////
private int idx = 1;
private int val = 1;
private int[] solution2(TreeNode root){
inOrder(root);
return result;
}
/**
* 中序遍历
* @param root
*/
private void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
if(root.val != (val++)){
result[idx--] = root.val;
}
inOrder(root.right);
}
}
发表于 2025-01-07 19:46:23
回复(0)
其实这道题问的是中序遍历，因为在中序遍历的情况下，数组是递增的，一旦出现元素互换，必定导致首尾各自出现一个局部极大值，因此，使用中序遍历获得数组排序后，使用两个指针分别从首尾两端检测，检查到不满足递增性质的元素就是被交换的元素
class Solution {
vector<int> path;
void dfs(TreeNode* root) {
if (root->left) dfs(root->left);
path.push_back(root->val);
if (root->right) dfs(root->right);
}
public:
vector<int> findError(TreeNode* root) {
dfs(root);
for (int &i : path) cout << i << ' ';
int l = 0, r = path.size() - 1;
while (l < r+1) {
if (path[l] < path[l+1]) l++;
else if (path[r-1] < path[r]) r--;
else break;
}
return {path[r], path[l]};
}
};
发表于 2024-09-23 23:25:12
回复(0)
脑溢血解法：不管错乱的节点是否相邻，复杂度高一些
// 中序遍历，把错位的找出来
public static int[] findError(TreeNode root) {
// write code here
ArrayList<Integer> res = new ArrayList<>();
midOrder(root, res);
ArrayList<Integer> copy = new ArrayList<>(res);
copy.sort(Comparator.comparingInt(o -> o));
// 找到乱序的两个位置
int[] ret = new int[2];
for (int i = 0; i < res.size(); i++) {
if(!res.get(i).equals(copy.get(i))){
ret[0] = copy.get(i);
ret[1] = res.get(i);
break;
}
}
return ret;
}
private static void midOrder(TreeNode root, List<Integer> res) {
if (root == null)
return;
midOrder(root.left, res);
res.add(root.val);
midOrder(root.right, res);
}
发表于 2024-06-04 11:58:17
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类 the root
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
#include <limits.h>
int arrar[100000] = {0};
int errArry[2] = {0,0};
int idxArry = 0;
void inorder(struct TreeNode* root)
{
if (root == NULL) {
return;
}
inorder(root->left);
arrar[idxArry++] = root->val;
inorder(root->right);
}
void findReplace(int * arr, int size)
{
int tmp_low = -1;
int tmp_high = -1;
for (int i = 0; i < size - 1; i++) {
if (arr[i] > arr[i + 1]) {
tmp_low = arr[i + 1];
if (tmp_high < 0) {
errArry[1] = arr[i]; //gretter val
tmp_high = 1;
} else {
break;
}
}
}
errArry[0] = tmp_low;
}
int* findError(struct TreeNode* root, int* returnSize ) {
// write code here
inorder(root);
findReplace(arrar, idxArry);
*returnSize = 2;
return errArry;
}
发表于 2024-05-29 21:52:21
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
TreeNode preNode = null;
TreeNode firstNode = null;
TreeNode secondNode = null;
public void inorder(TreeNode node) {
if (node == null) {
return;
}
inorder(node.left);
if (preNode != null && preNode.val > node.val) {
if (firstNode == null) {
firstNode = preNode;
}
secondNode = node;
}
preNode = node;
inorder(node.right);
}
public int[] findError (TreeNode root) {
inorder(root);
return firstNode.val < secondNode.val ?
new int[] {firstNode.val, secondNode.val} :
new int[] {secondNode.val, firstNode.val};
}
}
发表于 2024-05-13 21:53:26
回复(0)
public class Solution {
public int[] findError (TreeNode root) {
List<Integer> list = new ArrayList<>();
midOrder(list, root);
int size = list.size();
int numa = -1, numb = 0;
for(int i=1;i<size-1;i++){
if(numa!=0 && list.get(i) < list.get(i-1))
numa = list.get(i);
if(numb==0 && list.get(i) > list.get(i+1))
numb = list.get(i);
}
if(list.get(0) > list.get(1))
numb = list.get(0);
if(list.get(size-1) < list.get(size-2))
numa = list.get(size-1);
return new int[]{numa, numb};
}
public static void midOrder(List<Integer> list, TreeNode root){
if(root != null){
midOrder(list, root.left);
list.add(root.val);
midOrder(list, root.right);
}
}
} 获取二叉树中序遍历的结果，从前往后第一个比后一个数大的数为较大的交换数，从后往前第一个比前一个数小的数为较小的交换数
编辑于 2024-03-19 18:10:57
回复(0)
int minVal=Integer.MIN_VALUE ,p1=0 ,p2=0;
public int[] findError (TreeNode root) {
// write code here
dfs(root);
return new int[]{p2 ,p1};
}
public void dfs(TreeNode root){
if(root==null){
return;
}
dfs(root.left);
if(minVal>root.val){
if(p1==0){
p1=minVal;
p2=root.val;
}else{ // 如果第二次出现了逆序，则第二次逆序的小值为错误节点
p2=root.val;
}
}
minVal=root.val;
dfs(root.right);
}
编辑于 2024-03-17 14:37:47
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类 the root
* @return int整型一维数组
*/
public int[] findError (TreeNode root) {
// write code here
// 中序遍历有序
Deque<TreeNode> queue = new ArrayDeque<>();
List<Integer> list = new ArrayList<>();
TreeNode cur = root;
while(cur != null || !queue.isEmpty()) {
if(cur != null) {
queue.offerLast(cur);
cur = cur.left;
} else {
cur = queue.pollLast();
list.add(cur.val);
cur = cur.right;
}
}
int[] res = new int[2];
for(int i = 0; i < list.size() - 1; i++) {
if(list.get(i) > list.get(i + 1)) {
res[0] = i + 1;
break;
}
}
for(int i = list.size() - 1; i > 0; i--) {
if(list.get(i) < list.get(i - 1)) {
res[1] = i + 1;
break;
}
}
return res;
}
}
编辑于 2024-02-03 15:10:59
回复(0)
#include <vector>
class Solution {
public:
vector<int>list;
void find(TreeNode* root)
{
if(root)
{
find(root->left);
list.push_back(root->val);
find(root->right);
}
}
vector<int> findError(TreeNode* root) {
find(root);
vector<int>ans;
int j=0;
for(int i=0;i<list.size()-1;i++){
if(list[i]>list[i+1])
{
j=i;
break;
}
}
ans.push_back(list[j]);
int minn=list[j+1];
for(int i=j+1;i<list.size();i++){
minn=min(minn,list[i]);
}
ans.push_back(minn);
sort(ans.begin(),ans.end());
return ans;
}
};
发表于 2023-10-13 15:31:19
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类 the root
* @return int整型vector
*/
vector<int> v;
vector<int> findError(TreeNode* root) {
// write code here
dfs(root);
vector<int> t = v;
sort(t.begin(), t.end());
vector<int> idxV;
for (int i = 0; i < t.size(); ++i) {
if (t[i] != v[i]) {
idxV.push_back(t[i]);
}
}
return idxV;
}
void dfs(TreeNode* root) {
if (root == nullptr) return;
dfs(root->left);
v.push_back(root->val);
dfs(root->right);
}
};
发表于 2023-08-26 23:11:14
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类 the root
* @return int整型一维数组
*/
public int[] findError (TreeNode root) {
// write code here
if(root==null){
return null;
}
ArrayList<Integer> list=new ArrayList<>();
mid(root,list);
int arr[]=new int[2];
for(int i=0;i<list.size()-1;i++){
for(int j=i+1;j<list.size();j++){
//交换后判断是否递增
int tmp=list.get(i);
list.set(i,list.get(j));
list.set(j,tmp);
if(isUP(list)==true){
arr[0]=list.get(i);
arr[1]=list.get(j);
return arr;
//不符合递增就变回去进行下一轮判断
}else{
tmp=list.get(i);
list.set(i,list.get(j));
list.set(j,tmp);
}
}
}
return null;
}
public void mid(TreeNode root,ArrayList<Integer> list){
if(root==null){
return;
}
mid(root.left,list);
list.add(root.val);
mid(root.right,list);
}
public boolean isUP(ArrayList<Integer> list){
for(int i=1;i<list.size();i++){
if(list.get(i)<list.get(i-1)){
return false;
}
}
return true;
}
}
发表于 2023-06-16 11:03:03
回复(0)
package main
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
*
* @param root TreeNode类 the root
* @return int整型一维数组
*/
func findError( root *TreeNode ) []int {
var a,b int
arr:=order(root)
for i,x:=range arr{
if i>0&&x<arr[i-1]{
if a==0{
a,b=arr[i-1],x
}else{
b=x
break
}
}
}
if a>b{
return []int{b,a}
}
return []int{a,b}
}
func order(root *TreeNode)[]int{
if root==nil{
return nil
}
ans:=[]int{}
ans=append(ans,order(root.Left)...)
ans=append(ans,root.Val)
ans=append(ans,order(root.Right)...)
return ans
}
发表于 2023-03-29 17:17:42
回复(0)
两种情况：
- 两个交换的节点不相邻，那么会产生两次： pre.val > cur.val的情况
只需要把这两次 记录下来即可
2. 两个交换的节点相邻，那么只会产生一次： pre.val > cur.val
两种情况可以合在一起考虑，即第一次发生 pre.val > cur.val时，记录res = {cur.val,pre.val}
如果后面再发生pre.val > cur.val，则替换 cur.val
public int[] findError (TreeNode root) {
// write code here
dfs(root);
return res;
}
int[] res = new int[2];
int cnt = 1;
TreeNode pre = null;
public void dfs(TreeNode cur){
if(cur == null){
return;
}
dfs(cur.left);
if(pre == null){
pre = cur;
dfs(cur.right);
}
else{
if(pre.val > cur.val){
if(cnt > 0){
res[cnt] = pre.val;
res[0] = cur.val;
}
else{
res[cnt] = cur.val;
}
cnt --;
if(cnt <0){
return;
}
}
pre = cur;
dfs(cur.right);
}
}
发表于 2023-03-20 21:51:04
回复(0)
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return int整型vector
*/
int curError=0;
int error1=-1,error2=-2;
int pre=-1;
vector<int> findError(TreeNode* root) {
// write code here
if(!root) return {};
dfs(root);
if(error1>error2) swap(error1,error2);
return {error1,error2};
}
void dfs(TreeNode* root){
if(!root) return;
if(curError==2) return;
dfs(root->left);
if(pre==-1) pre=root->val;
else{
if(pre>root->val&&curError==0){
error1=pre;
error2=root->val;
curError++;
}
else if(pre>root->val&&curError==1){
error2=root->val;
curError++;
}
}
pre=root->val;
dfs(root->right);
}
};
发表于 2022-08-03 10:19:10
回复(0)
莫里斯 O1
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return int整型vector
*/
TreeNode * rem1 = nullptr;//第一个 不为升序 的 大节点
TreeNode * rem2 = nullptr;//rem1 的相邻节点
TreeNode * rem3 = nullptr;// 第二个 不为升序的 小节点
TreeNode * t_pre = nullptr;
vector<int> findError(TreeNode* root) {
// write code here
if (root == nullptr ) return {};
//vector<TreeNode *> res;
moris(root/*, res*/);
if (rem3 == nullptr) return {rem2 -> val, rem1 -> val};
return {rem3 -> val,rem1 -> val};
}
// 莫里斯遍历: 搭桥拆桥
// 前序和中序 都是: 左子树的节点会到达两次
// ==> 第一次 到达就打印 是前序 第二次到达就打印 是中序
// ==> 右子节点只会到达一次: 到达就打印
// 后续遍历 把所有的left 和right换一下jiuok
void moris (TreeNode * root/*,vector<TreeNode *> & res*/) {
if (root == nullptr) return ;
TreeNode * cur = root;
while (cur) {
if (cur -> left == nullptr) {
//res.push_back(cur);
if (t_pre == nullptr) {
t_pre = cur;
}else {
if (cur -> val < t_pre -> val) {
if (rem1 == nullptr) {
rem1 = t_pre;
rem2 = cur;
}else {
rem3 = cur;
}
}
t_pre = cur;
}
cur = cur -> right;
} else {
TreeNode * pre = cur -> left;
while (pre -> right != nullptr && pre -> right != cur) {
//pre-> right -== null 说明是第一次到达
// pre-> right == cur 说明是第二次到达
pre = pre -> right;
}
if (pre -> right == nullptr) {
//第一次到达
pre -> right = cur;
cur = cur -> left;
}else {
pre -> right = nullptr;
if (t_pre == nullptr) {
t_pre = cur;
}else {
if (cur -> val < t_pre -> val) {
if (rem1 == nullptr) {
rem1 = t_pre;
rem2 = cur;
}else {
rem3 = cur;
}
}
t_pre = cur;
}
//res.push_back(cur);
cur = cur -> right;
}
}
}
return ;
}
};
编辑于 2022-07-13 17:02:10
回复(0)
问题信息
难度：
47条回答
211收藏
7547浏览
通过挑战的用户
查看代码-
2023-01-13 12:12:50 -
2022-10-07 22:35:07
-
2022-09-26 01:06:08 -
2022-09-18 20:48:04
-
2022-09-18 12:53:47
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
