首页 > 试题广场 >

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

[编程题]找到搜索二叉树中两个错误的节点
  • 热度指数：14009 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
C++
木析头像 木析 
/**
 * 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)
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)
Python 3
昊天明月头像 昊天明月
正常的二叉搜索树中序遍历一定是一个递增的序列，交换之后一定不递增了，所以我们找中序遍历第一个比后面值大的值，再找后面比这个值小的最后一个值。
发表于 2023-05-19 17:00:43 回复(0)
牛客996957770号头像 牛客996957770号 
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)
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)
牛客2024007号头像 牛客2024007号 
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)
fatzard头像 fatzard 
#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)
asdfasdq头像 asdfasdq 
/**
 * 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)
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)
Go
小谷围做题家头像 小谷围做题家 
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)
牛客565269855号头像 牛客565269855号

两种情况：

  1. 两个交换的节点不相邻，那么会产生两次： 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)
C++
Getchance头像 Getchance 
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)
C++
碎叶头像 碎叶
无论递归遍历还是非递归遍历，这额外空间复杂度都不能达到O（1）
发表于 2022-07-02 12:46:07 回复(0)
C++
plume95头像 plume95 
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return int整型vector
     */
    vector<int> findError(TreeNode* root) {
        // write code here
        vector<int> err;
        search(root, err);
        vector<int> tmp(err);
        vector<int> ans;
        ans.reserve(2);
        sort(tmp.begin(), tmp.end());
        
        for(int i = 0; i < err.size()-1; ++i)
        {
            if(err[i] != tmp[i]) 
            {
                ans.push_back(tmp[i]);
                ans.push_back(err[i]);
                break;
            }
        }
        return ans;
    }
    
    void search(TreeNode* node, vector<int>& err)
    {
        if(node == nullptr) return;
        search(node->left, err);
        err.push_back(node->val);
        search(node->right, err);
        return;
    }
};

笨方法

发表于 2022-04-29 17:10:56 回复(0)
Python 3
想搞机器学习的小白头像 想搞机器学习的小白
python 
class Solution:
    def findError(self , root: TreeNode) -> List[int]:
        # write code here
        def dfs(root):
            if not root:return 
            dfs(root.left)   
            if root.val !=self.count:self.res.append(root.val)
            self.count +=1
            dfs(root.right)
        self.res,self.count =[],1
        dfs(root)
        self.res.sort()
        return self.res

发表于 2022-04-06 23:28:28 回复(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)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def findError(self , root: TreeNode) -> List[int]:
        # write code here
        res=[]
        def inorder(root):
            if not root:
                return 
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
            return res
        res=inorder(root)
        exchange=[]
        index=[]
        for i in range(len(res)-1):
            if len(index)<1:
                if res[i]>res[i+1]:
                    exchange.append(res[i])
                    index.append(i)
            elif len(index)>=1 and i>index[0]+1:
                if res[i]<res[i+1] and res[i]<res[i-1]:
                    exchange.append(res[i])
                    index.append(i)
#        return res
        if len(exchange)==2:
            return  [exchange[1],exchange[0]]
        elif len(exchange)==1:
            return [res[index[0]+1],exchange[0]]
       

发表于 2022-01-11 07:35:37 回复(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)
Go
bigkai头像 bigkai
package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 
 * @param root TreeNode类 the root
 * @return int整型一维数组
*/
var idx, prev, tmp int
const MIN_VALUE  = -65535
func findError( root *TreeNode ) []int {
    idx, prev, tmp = 1, MIN_VALUE, 0
    res := make([]int, 2)
    inorder(root, res)
    if idx == 0 {
        res[idx] = tmp
    }
    return res
}

func inorder(root *TreeNode, res []int)  {
    if root == nil {
        return
    }    
    inorder(root.Left, res)
    if prev != MIN_VALUE {
        if root.Val < prev {
            if idx == 1 {
                res[idx] = prev
                tmp = root.Val
            } else {
                res[idx] = root.Val
                tmp = prev
            }
            idx--
        }
    }

    prev = root.Val
    inorder(root.Right, res)
}
发表于 2021-08-14 11:04:30 回复(0)
提交观点

问题信息

树 dfs
难度：
42条回答 4835浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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