牛客题霸 找到搜索二叉树中两个错误的节点

题目描述

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

示例1

输入

{1,2,3}

返回值

[1,2]

备注:

1 leq n leq 5 	imes 10^51≤n≤5×105

说明：本题目包含复杂数据结构TreeNode，

Python代码：

# 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 ):
        # write code here
        if not root:
            return []
        res = []
        stack = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            res.append(root.val)
            root = root.right
        ans = []
        for i in range(len(res)-2, -1, -1):
            if res[i] > res[i+1]:
                ans.append(res[i+1])
                break
        for i in range(1, len(res)):
            if res[i] < res[i-1]:
                ans.append(res[i-1])
                break
        return ans