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?
Solution
- 中序遍历应该返回递增序列
- 若非叶子节点与叶子搞错了，则会出现一个递减序列 (self.prev, self.n1)
- 若非叶子与非叶子搞错了，则出现２个递减序列(self.n1, self.n2)
(Recover-Binary-Search-Tree.py) download
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
| # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
self.n1 = None
self.n2 = None
self.prev = None
self.tranverse(root)
self.n1.val,self.n2.val = self.n2.val, self.n1.val
return
def tranverse(self, node):
if node == None:
return
# 中序遍历应该得到递增序列
self.tranverse(node.left)
# 有可能出现１个或２个递减情况
if self.prev and self.prev.val > node.val:
self.n2 = node
if self.n1 == None:
self.n1 = self.prev
self.prev = node
self.tranverse(node.right)
|