一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)
搜索二叉树：满足每个节点的左子节点小于当前节点，右子节点大于当前节点。
样例1图
样例2图
数据范围：
,节点上的值满足 
，保证每个value各不相同
进阶：空间复杂度 )
，时间复杂度 )
[编程题]找到搜索二叉树中两个错误的节点
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)
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)
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
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)
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整型一维数组
*/
TreeNode first=null;
TreeNode second=null;
TreeNode pre=new TreeNode(Integer.MIN_VALUE);
public int[] findError (TreeNode root) {
// write code here
//中序遍历找到这两个节点
inorder(root);
// TreeNode tem=first;
// first.val=second.val;
// second.val=tem.val;
return new int[]{second.val,first.val};
}
public void inorder(TreeNode root){
if(root==null){
return;
}
inorder(root.left);
if(root.val<pre.val){
//出现错误的情况
if(first==null){
first=pre;
}
second=root;
}
pre=root;
inorder(root.right);
}
}
发表于 2022-01-29 11:54:18
回复(0)
import java.util.*;
/**
七刷
解题思路：
1. 先用中序遍历遍历树，得到一个部分排序数组，该数组中有两个数交换了位置，
现在的问题变成了从一个部分有序的数组中找出交换了位置的那两个数
2. 因为此时的情况必定是一个小的数放到了后面，一个大的数放到了前面
所以从左往右找那个大的数，并记录下索引，从右往左找小的那个数，并且索引值必大于前面记录下的索引
*/
public class Solution {
List<Integer> list = new ArrayList();
public int[] findError (TreeNode root) {
int[] result = new int[2];
if(root == null) {
return result;
}
findErrorHelper(root);
int i, j;
for(i = 0; i < list.size() - 1; i++) {
if(list.get(i) > list.get(i + 1)) {
result[1] = list.get(i);
break;
}
}
for(j = list.size() - 1; j > i; j--) {
if(list.get(j) < list.get(j - 1)) {
result[0] = list.get(j);
break;
}
}
return result;
}
private void findErrorHelper(TreeNode root) {
if(root != null) {
findErrorHelper(root.left);
list.add(root.val);
findErrorHelper(root.right);
}
}
}
发表于 2021-10-01 21:23:27
回复(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 ArrayList<Integer> arr = new ArrayList<>();
public int[] findError (TreeNode root) {
// write code here
int[] ans = new int[2];
inOrder(root);
ArrayList<Integer> reversed = new ArrayList<>();
for(int i = 0; i < arr.size()-1; i++) {
if(arr.get(i) > arr.get(i+1)) {
reversed.add(i);
}
}
if(reversed.size() == 1) {
int idx = reversed.get(0);
ans = new int[]{arr.get(idx), arr.get(idx+1)};
}
if(reversed.size() == 2) {
int idx1 = reversed.get(0), idx2 = reversed.get(1)+1;
ans = new int[]{arr.get(idx1), arr.get(idx2)};
}
Arrays.sort(ans);
return ans;
}
public void inOrder(TreeNode root) {
if(root == null) return;
inOrder(root.left);
arr.add(root.val);
inOrder(root.right);
}
}
发表于 2021-08-09 21:35:51
回复(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 Solution {
int idx = 1;
int prev = Integer.MIN_VALUE;
int tmp = 0;
public int[] findError (TreeNode root) {
int[] res = new int[2];
inorder(root, res);
if (idx == 0) {
res[idx] = tmp;
}
return res;
}
public void inorder(TreeNode root, int[] res) {
if (root == null) {
return;
}
inorder(root.left, res);
if (prev != Integer.MIN_VALUE) {
if (root.val < prev) {
if (idx == 1) {
res[idx--] = prev;
tmp = root.val;
}else {
res[idx--] = root.val;
tmp = prev;
}
}
}
prev = root.val;
inorder(root.right, res);
}
}
发表于 2021-01-18 22:30:08
回复(0)
问题信息
难度：
9条回答
211收藏
7726浏览
通过挑战的用户
查看代码-
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号
