- """
- 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,null,2]
- 1
- /
- 3
- 11 2
- Output: [3,1,null,null,2]
- 3
- /
- 1
- 17 2
- Example 2:
- Input: [3,1,4,null,null,2]
- 3
- / 22 1 4
- /
- 2
- Output: [2,1,4,null,null,3]
- 2
- / 28 1 4
- /
- 3
- """"""
- 自己 AC 了一种笨方法:
- 首先对二叉树中序遍历得到 inorder
- 再对 inorder 排序得到 s_inorder
- 比较两个列表的差异, 如果不相等, 将两个不相等的值保存到 x,y
- 第二次遍历二叉树, 将值为 x 的设为'a', 值为 y 的设为 x.(这里不知道怎么交换值)
- 第三次遍历二叉树, 将值为'a'的设为 y
- """
- class TreeNode:
- def __init__(self, x):
- self.val = x
- self.left = None
- self.right = None
- class Solution1:
- def recoverTree(self, root):
- """
- Do not return anything, modify root in-place instead.
- """
- stack = []
- cur = root
- inorder = []
- while cur or stack:
- if cur:
- stack.append(cur)
- cur = cur.left
- else:
- cur = stack.pop()
- inorder.append(cur.val)
- cur = cur.right
- s_inorder = sorted(inorder)
- for i in range(len(s_inorder)):
- if s_inorder[i] != inorder[i]:
- x = s_inorder[i]
- y = inorder[i]
- break
- queue = []
- queue.append(root)
- while queue:
- node = queue.pop(0)
- if node.val == x:
- node.val = 'a'
- if node.val == y:
- node.val = x
- if node.left:
- queue.append(node.left)
- if node.right:
- queue.append(node.right)
- newqueue = []
- newqueue.append(root)
- while newqueue:
- _node = newqueue.pop(0)
- if _node.val == 'a':
- _node.val = y
- if _node.left:
- newqueue.append(_node.left)
- if _node.right:
- newqueue.append(_node.right)
- """
- 解法二: 可以再解法一得到有序的 s_inorder 后
- 将 s_inorder 覆盖到整个二叉树
- """
- class Solution2:
- def recoverTree(self, root):
- """
- Do not return anything, modify root in-place instead.
- """
- stack = []
- cur = root
- inorder = []
- while cur or stack:
- if cur:
- stack.append(cur)
- cur = cur.left
- else:
- cur = stack.pop()
- inorder.append(cur.val)
- cur = cur.right
- s_inorder = sorted(inorder)
- i = 0
- _cur = root
- _stack = []
- while _cur or _stack:
- if _cur:
- _stack.append(_cur)
- _cur = _cur.left
- else:
- _cur = _stack.pop()
- _cur.val = s_inorder[i]
- i += 1
- _cur = _cur.right
- if __name__ == '__main__':
- root = TreeNode(1)
- node1 = TreeNode(3)
- node2 = TreeNode(2)
- root.left = node1
- node1.right = node2
- ans = Solution1()
- print(ans.recoverTree(root))
来源: http://www.bubuko.com/infodetail-3446703.html