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

[编程题]找到搜索二叉树中两个错误的节点

热度指数：14802 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)

搜索二叉树：满足每个节点的左子节点小于当前节点，右子节点大于当前节点。

样例1图

样例2图

数据范围： $3 \le n \le 100000$ ,节点上的值满足 $1 \le val \le n$ ，保证每个value各不相同

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3}

输出

[1,2]

说明

如题面图

示例2

输入

{4,2,5,3,1}

输出

[1,3]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python 3

昊天明月

正常的二叉搜索树中序遍历一定是一个递增的序列，交换之后一定不递增了，所以我们找中序遍历第一个比后面值大的值，再找后面比这个值小的最后一个值。

发表于 2023-05-19 17:00:43 回复(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)

Python 3

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)