Leetcode99 恢复二叉搜索树

题目描述

file

方法一

class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        stack = []
        pre,x,y = None,None,None
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if pre and pre.val > root.val:
                y = root
                if x == None:
                    x = pre
            pre = root
            root = root.right
        x.val, y.val = y.val, x.val

 

O(1)解法:Morris 遍历算法

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        x, y, prev = None, None, None
        while root:
            if root.left:
                succ = root.left
                while succ.right and succ.right != root:
                    succ = succ.right
                if not succ.right:
                    succ.right = root
                    root = root.left
                    continue
                succ.right = None
            # 访问
            if prev and prev.val > root.val:
                if not x:
                    x = prev
                y = root
            prev = root
            root = root.right
        x.val, y.val = y.val, x.val

 

思路:

原地解法参考 官方题解

笔记&回顾:

中序遍历非递归写法

	stack = []
	while root or stack:
		while root:
			stack.append(root.left)
			root = root.left
		root = stack.pop()
		root = root.right

 

Morris中序

def inorder(root):
	if not root: return
	p = root; prenode = None
	while p:
		if p.left:
			prenode = p.left
			while prenode.right and prenode.right != p:
				prenode = prenode.right
			if not prenode.right:			#建立链接方便回溯
				prenode.right = p
				p = p.left
				continue
			if prenode.right == p:
				print(p.val)				#打印
				prenode.right = None		#回溯完成删除多余链接
		if not p.left: print(p.val)			#打印
		p = p.right