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

from pickle import NONE
# 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 findError(self , root: TreeNode) -> List[int]:
        # write code here
        # 搜索二叉树中序遍历一定保持升序
        ret = self.search(root)   
		# 从前往后找异常值
        for i in range(len(ret)-1):
            if ret[i] > ret[i+1]:
                break
		# 从后往前找异常值(和前面的异常值对比，符合条件返回)
        for j in range(len(ret)-1,i,-1):
            if ret[j] < ret[i]:
                break
        return [ret[j], ret[i]]

    def search(self, root):
        ret = []
        if root:
            ret.extend(self.search(root.left))
            ret.append(root.val)
            ret.extend(self.search(root.right))
        return ret