关于算法:每日一题调整搜索二叉树中两个错误的节点

一棵二叉树本来是搜寻二叉树，然而其中有两个节点调换了地位，使得这棵二叉树不再是搜寻二叉树，请找到这两个谬误节点并返回。

已知二叉树中所有节点的值都不一样，给定二叉树的头节点 head，返回一个长度为 2 的二叉树节点类型数组 errs，errs[0] 示意一个谬误节点，errs[1] 示意另一个谬误节点。

解法一：递归

如下图对搜寻二叉树进行中序遍历，能够失去一个升序数组。如果搜寻二叉树中有两个节点调换为了地位，那么失去的数组，升序肯定被毁坏了。

如下图：如果节点 2 与节点 4 调换了地位，失去的数组中有两个逆序对。

• 第一个谬误节点：第一次降落的前一个节点。
• 第二个谬误节点：最初一次降落的一个节点。

如下图：如果节点 2 与节点 5 调换了地位，失去的数组中有两个逆序对。

• 第一个谬误节点：第一次降落的前一个节点。
• 第二个谬误节点：最初一次降落的一个节点。

如下图：如果节点 2 与节点 3 调换了地位，失去的数组中有一个逆序对。

数组无论有两个逆序对还是只有一个逆序对，谬误节点都满足下边的法则。

• 第一个谬误节点：第一次降落的前一个节点。
• 第二个谬误节点：最初一次降落的一个节点。

class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightdef find_error_nodes(root: TreeNode):    return inorder(root, None, None)def inorder(node, first, second):    if node:        first, second = inorder(node.left, first, second)        if node.left and node.left.val > node.val:            second = node            if not first: first = node.left        first, second = inorder(node.right, first, second)        if node.right and node.right.val < node.val:            second = node.right            if not first: first = node    return [first, second]

解法二：非递归

def find_error_nodes2(root: TreeNode):    if not root: return    stack = []    first = None    second = None    pre = None    while root or stack:        # 从根节点开始，始终找它的左子树        if root:            stack.append(root)            root = root.left        else:            # while完结示意以后节点node为空，即前一个节点没有左子树了            root = stack.pop()            if pre and pre.val > root.val:                second = root                if not first: first = pre            pre = root            # 开始查看它的右子树            root = root.right    return [first, second]

起源