Description:

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

Recover the tree without changing its structure.

Example 1:

Example 2:

Follow up:

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

Solutions:

野路子Solution: 雖然解出來了返干，但是果然運(yùn)行速度太慢了

NOTE: 先用dfs遍歷二叉樹键痛，不斷check每個node丝里，標(biāo)記出來有問題的node。如果搜索到底部钮热，則保存當(dāng)前move_hist到move_ls，當(dāng)前correct_hist到corr_ls烛芬。 找出1-2個最特征的move_hist隧期。如果是2個飒责，則說明錯誤的兩個node在某個parent的左右兩邊，否則說明在一條鏈上仆潮。

• case1: 如果是左右兩邊則第兩條move_hist第一個出問題的node的value互換宏蛉。
• case2: 如果是在一條鏈上，則需要利用move_hist構(gòu)建在該鏈上的當(dāng)前錯誤的排序性置，同時保存node和node.val到兩個list拾并，然后對node.val的list排序，最后把這些值賦給node的list鹏浅。

一些測試集：

• [20,35,30,5,15,25,10,3,7,13,17,23,27,33,37]
• [30,10,20,5,15,25,35,3,7,13,17,23,27,33,37]
• [27,10,30,5,15,25,35,3,7,13,17,23,20,33,37,null,null,null,null,null,null,null,null,null,null,26,28]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        def check(node,mini,maxi):
            if node == None:
                return [True,True]
            error = [None,None]
            if node.left != None and (node.left.val > node.val or node.left.val < mini):
                error[0] = False
            else:
                error[0] = True
            if node.right != None and (node.right.val < node.val or node.right.val > maxi):
                error[1] = False
            else:
                error[1] = True
            return error
        
        corr_ls = []
        move_ls = []
        def dfs(move_hist,correct_hist,node,mini,maxi):
            left_corr,right_corr = check(node,mini,maxi)
            
            if node.left != None:
                if left_corr == False:
                    dfs(move_hist+"l",correct_hist+[left_corr],node.left,-math.inf,math.inf)
                else:
                    dfs(move_hist+"l",correct_hist+[left_corr],node.left,mini,node.val)
            if node.right != None:
                if right_corr == False:
                    dfs(move_hist+"r",correct_hist+[right_corr],node.right,-math.inf,math.inf)
                else:
                    dfs(move_hist+"r",correct_hist+[right_corr],node.right,node.val,maxi)
            if node.left == None and node.right == None:
                corr_ls.append(correct_hist)
                move_ls.append(move_hist)
        
        dfs("",[],root,-math.inf,math.inf)
        
        problem_path = []
        problem_corr = []
        for i in range(len(corr_ls)-1,-1,-1):
            if False not in corr_ls[I]:
                continue
            for j in range(len(corr_ls[i])-1,-1,-1):
                if corr_ls[i][j] == False:
                    break
            cache = move_ls[i][:j+1]
            if not problem_path:
                problem_path.append(cache)
                problem_corr.append(corr_ls[I])
            else:
                if len(cache) > len(problem_path[-1]):
                    if problem_path[-1] == cache[:len(problem_path[-1])]:
                        problem_path[-1] = cache
                        problem_corr[-1] = corr_ls[I]
                    else:
                        problem_path.append(cache)
                        problem_corr.append(corr_ls[I])
                elif problem_path[-1][:len(cache)] != cache:
                    problem_path.append(cache)
                    problem_corr.append(corr_ls[I])
                    
#         print(problem_path,"\n",problem_corr)
        
        def navigate(path,corr):
            cache = root
            for i,s in enumerate(path):
                if s == "l":
                    cache = cache.left
                else:
                    cache = cache.right
                if corr[i] == False:
                    break
            return cache
        
        def rearrange(path):
            cache = root
            value = [root.val]
            node = [root]
            last = 0
            for s in path:
                if s == "l":
                    cache = cache.left
                    node = node[:last] + [cache] + node[last:]
                    value = value[:last] + [cache.val] + value[last:]
                else:
                    cache = cache.right
                    node = node[:last+1] + [cache] + node[last+1:]
                    value = value[:last+1] + [cache.val] + value[last+1:]
                    last += 1
                    
            # print(value)
            value.sort()
            # print(value)
            for i in range(len(value)):
                node[i].val = value[I]
        
        if len(problem_path) == 2:
            n1 = navigate(problem_path[0],problem_corr[0])
            n2 = navigate(problem_path[1],problem_corr[1])
            # print(n1.val,n2.val)
            n1.val,n2.val = n2.val,n1.val
            # print(n1.val,n2.val)
        else:
            rearrange(problem_path[0])

Runtime: 104 ms, faster than 5.23% of Python3 online submissions for Recover Binary Search Tree.
Memory Usage: 13.7 MB, less than 5.78% of Python3 online submissions for Recover Binary Search Tree.

Solution2: O(n), inspired by https://www.cnblogs.com/grandyang/p/4298069.html 解法1

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        
        def dfs(node):
            if node.left == None and node.right == None:
                return [node.val],[node]
            val = []
            nod = []
            if node.left != None:
                left_ret = dfs(node.left)
                val += left_ret[0]
                nod += left_ret[1]
            val += [node.val]
            nod += [node]
            if node.right != None:
                right_ret = dfs(node.right)
                val += right_ret[0]
                nod += right_ret[1]
            return val,nod
        
        value_ls,node_ls = dfs(root)
        value_ls.sort()
        for i,n in enumerate(node_ls):
            n.val = value_ls[I]

Runtime: 76 ms, faster than 74.21% of Python3 online submissions for Recover Binary Search Tree.
Memory Usage: 13.5 MB, less than 40.00% of Python3 online submissions for Recover Binary Search Tree.

Solution3: inorder traversal, O(n) space 不用遞歸

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        
        value = []
        node = []
        stack = []
        curr = root
        while curr != None or stack:
            if curr != None:
                stack.append(curr)
                curr = curr.left
            else:
                curr = stack.pop()
                value.append(curr.val)
                node.append(curr)
                curr = curr.right
                
        value.sort()
        for i,n in enumerate(node):
            n.val = value[I]

Runtime: 80 ms, faster than 53.35% of Python3 online submissions for Recover Binary Search Tree.
Memory Usage: 13.5 MB, less than 40.00% of Python3 online submissions for Recover Binary Search Tree.

Solution4: Morris inorder traversal O(1) space

inspired by http://fisherlei.blogspot.com/2012/12/leetcode-recover-binary-search-tree.html and
https://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/

NOTE: 不用保存完整的traversal history嗅义，只需要保存last visited node（叫prev）就行了，這個last node初始化是None隐砸。然后凡是prev比curr大之碗，就把這倆按順序放到一個list里（叫problem）。兩種情況：

不論那種情況季希，最終只需要把problem的開頭和結(jié)尾的node的value互換就行了褪那！

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        
        curr = root
        prev = None
        
        def FindPredecessor(node):
            cache = node.left
            while cache.right != None and cache.right != node:
                cache = cache.right
            return cache
        
        problem = []
        
        while curr != None:
            if curr.left == None:
                if prev != None and curr.val < prev.val: # 先比較
                    problem += [prev,curr] # 先比較
                prev = curr # 先比較，之前這一步是ret.append(curr.val)
                curr = curr.right
            else:
                pred = FindPredecessor(curr)
                if pred.right == None:
                    pred.right = curr
                    curr = curr.left
                else:
                    if prev != None and curr.val < prev.val: # 先比較
                        problem += [prev,curr] # 先比較
                    prev = curr # 先比較胖眷，之前這一步是ret.append(curr.val)
                    curr = curr.right
                    pred.right = None
                    
        p1,p2 = problem[0],problem[-1]
        p1.val,p2.val = p2.val,p1.val

Runtime: 68 ms, faster than 95.79% of Python3 online submissions for Recover Binary Search Tree.
Memory Usage: 13.3 MB, less than 90.00% of Python3 online submissions for Recover Binary Search Tree.