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

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

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

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

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。

以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

ps:节点的编号就是该节点的值。

输出描述:

请按升序输出这两个错误节点的值。

示例1

输入

输出

1 2

备注:

算法知识视频讲解

一只老风铃

发表于 2021-01-22 11:43:53

二叉搜索树，如果正确采取中序遍历，将是一个递增的序列。例如正确的中序情况：1 2 3 4 5那么交换其中任意两个节点情况：可以发现，其本质是寻找逆序对，可能只有一组1 3 2 4 5可能有两组：1 5 3 4 2 或 1 4 3 2 5 那么只需要中序遍历二叉树，找到逆序对，第一个数，最后一个数展开全文