python实现leetcode之99. 恢复二叉搜索树

解题思路

先中序遍历一下，将每个节点放入遍历队列中
再根据节点的值排序
然后zip遍历，其中有且仅有两个节点的值不想等，交换值即可

99. 恢复二叉搜索树

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        queue = []
        def in_order(tree):
            if not tree: return
            in_order(tree.left)
            queue.append(tree)
            in_order(tree.right)
        in_order(root)
        new_queue = sorted(queue, key=lambda n: n.val)
        for x, y in zip(queue, new_queue):
            if x != y:
                x.val, y.val = y.val, x.val
                break