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

#coding:utf-8
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 the root
# @return int整型一维数组
#
#1. 先用中序遍历遍历树，得到一个部分排序数组，该数组中有两个数交换了位置，
#现在的问题变成了从一个部分有序的数组中找出交换了位置的那两个数

#2. 因为此时的情况必定是一个小的数放到了后面，一个大的数放到了前面
#所以从左往右找那个大的数，并记录下索引，从右往左找小的那个数，并且索引值必大于前面记录下的索引。

class Solution:
    def __init__(self):
        self.path = []

    def findError(self , root ):
        # write code here
        ret = []
        if root == None:
            return [-1, -1]
        self.inOrder(root) 
        #find the wrond numbers
        n = len(self.path)
        for i in range(n - 1, 0, -1):
            post = self.path[i]
            pre = self.path[i - 1]
            if post < pre:
                ret.append(post)
                break
        for i in range(0, n - 1):
            pre = self.path[i]
            post = self.path[i + 1]
            if pre > post:
                ret.append(pre)
                break

        return ret

    def inOrder(self, node):
        stack = []
        while len(stack) > 0 or node != None:
            while node != None:
                stack.append(node)
                node = node.left 
            node = stack.pop()
            self.path.append(node.val)
            node = node.right
        print ("Inorder: ", self.path)
        return