Leetcode解题-Recover Binary Search Tree

发表于   |   分类于   |  

描述

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

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

分析

可以用中序遍历来做，记录上一个访问的元素，如果发现违反了正序则记录位置，遍历完之后把两个位置元素调换。时间O(n)，空间平均O(logn)，最坏O(n)。

追求空间O(1)的解法可以使用Morris遍历。

代码

普通中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        # inorder traversal
        cur = root
        ss = []
        prev = TreeNode(float('-inf'))
        first = second = None
        while ss or cur:
            if cur:
                ss.append(cur)
                cur = cur.left
            else:
                cur = ss.pop()
                # visit cur
                if cur.val < prev.val:
                    if not first:
                        first = prev
                    second = cur
                prev = cur
                cur = cur.right
        first.val, second.val = second.val, first.val

Morris遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        # inorder traversal
        cur = root
        prev = None
        first = second = None
        while cur:
            if not cur.left:
                # visit cur
                if prev and cur.val < prev.val:
                    if not first:
                        first = prev
                    second = cur
                prev = cur
                cur = cur.right
            else:
                node = cur.left
                while node.right and node.right != cur:
                    node = node.right
                if not node.right:
                    # not threaded yet
                    node.right = cur
                    cur = cur.left
                else:
                    # already threaded
                    node.right = None
                    # visit cur
                    if prev and cur.val < prev.val:
                        if not first:
                            first = prev
                        second = cur
                    prev = cur
                    cur = cur.right

        first.val, second.val = second.val, first.val

热评文章