首页 > 试题广场 >

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

[编程题]找到搜索二叉树中两个错误的节点
  • 热度指数：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，点此查看相关信息
算法知识视频讲解
添加回答
Java
牛客148901号头像 牛客148901号 
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)
Java
牛客839384289号头像 牛客839384289号 
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)
Java
梁山教父头像 梁山教父 
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)
Java
万里归途头像 万里归途 
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)
Java
惠灵顿靖头像 惠灵顿靖 
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)
Java
maple201809041428901头像 maple201809041428901 
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)
Java
阿尼亚瓦库瓦库头像 阿尼亚瓦库瓦库 
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)
Java
努力学习的中国好青年头像 努力学习的中国好青年 
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)
提交观点

问题信息

树 dfs
难度：
8条回答 5712浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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