题解 | #找到搜索二叉树中两个错误的节点#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 the root
# @return int整型一维数组
#
class Solution:
    def __init__(self) -> None:
		# 创建一个列表用于存储中序遍历的节点值
        self.res = []

    def findError(self, root: TreeNode) -> List[int]:
        # write code here
        if not root:
            return []
		# 获取中序排列的节点数据
        self.inorder(root)
		# 将错误的节点列表重新排序
		# 如果中序遍历的节点值与排序后的节点值不相等，则说明该节点是错误节点
		# 如： [3,2,1,4]  排序后是 [1,2,3,4]
		# 3 和 1 的节点值不相等，则说明这两个节点是错误节点 
        alstt = sorted(self.res)
        res_lst = []
        for l,r in zip(self.res, alstt):
            if l != r:
                res_lst.append(l)
		# 结果是从大到小排列的，因此倒序输出
        return res_lst[::-1]
    
    def inorder(self, root:TreeNode):
		# 中序遍历树，因为搜索树的中序遍历是从小到大排列的，因此只需要找到排序不正常的值即可
        if not root:
            return None
        self.inorder(root.left)
        self.res.append(root.val)
        self.inorder(root.right)