leetcode99 - recover binary search tree - hard

发布时间：2020-12-14 05:06:30 所属栏目：大数据来源：网络整理

导读：Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,2]? 1? /?3? ? 2Output: [3,1,2]? 3? /?1? ? 2 Example 2: Input: [3,4,2] 3 / 1 4? /? 2Output: [2,3

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,2]

?  1
? /
?3
? ?  2

Output: [3,1,2]

?  3
? /
?1
? ?  2

Example 2:

Input: [3,4,2]

  3
 / 1   4
?  /
? 2

Output: [2,3]

  2
 / 1   4
?  /
 ?3

思路： 找到两个大小有问题的点，交换位置即可。从最下面的左子树向上比较，因为最下面的左子树的值是最小的。如果遇到第一个顺序有问题的点，就把这个点和第二个遇到的有问题的点进行交换位置即可。
实现方法用stack。把全部root.left先append进去。到底之后，再pop出来一个root成为node。比较这个node和之后pop出来的root的值。如果这个值比之后的值要大，那说明node是找到的第一个位置有问题的点。
注意的是，后续需要把node.right再append进stack。

class Solution:
    def recoverTree(self,root: TreeNode) -> None:
        """
        Do not return anything,modify root in-place instead.
        """
        if not root: return root
        res,first,second = None,None,None
        stack = []
        
        while True:
            while root:
                stack.append(root)
                root = root.left  
            if not stack:
                break
            node = stack.pop()
            if res and res.val > node.val:
                if not first:
                    first = res
                second = node
            
            res = node
            root = node.right
        first.val,second.val = second.val,first.val

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!