一棵二叉樹原本是搜索二叉樹，但是其中有兩個節點調換了位置，使得這棵二叉樹不再是搜索二叉樹，請找到這兩個錯誤節點並返回。

已知二叉樹中所有節點的值都不一樣，給定二叉樹的頭節點 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 = right

def 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]

來源