BST

https://github.com/qiwsir/algorithm/blob/master/binary_tree.md
Binary Search Tree:

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  • 任意节点的左、右子树也分别为二叉查找树;
  • 没有键值相等的节点

BST最重要的特性: inorder traversal a bst, will get an sorted array.
http://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/

bstpasted image

插入节点:

如果target<node,继续遍历node的左叶子,如果左叶子没有。那么就插入。否则比较node的左叶子和target。每次插入的时候总是会插入的是叶子节点。

删除节点

三种情况,

  • 如果是叶子,直接删除。不会影响其他结构。
  • 如果删除的节点有一个child。那么直接将父节点指向删除之后的leaf。
  • 如果节点有两个children.那么找到该节点下的next biggest.然后交换过去。如删除70,那么将75交换过去。如删除30,那么将32交换过去。同时,将34作为40的left node

AVL树(自平衡二叉树)

AVL树是高度平衡的而二叉树。它的特点是:AVL树中任何节点的两个子树的高度最大差别为1

Recover Binary Search Tree

二叉搜索树里面两个节点被互换。如何找到并修正,要求空间复杂度为O(1)

空间复杂度为O(n)解法

参考:http://www.cnblogs.com/zuoyuan/p/3746594.html

  • 中序遍历二叉搜索树,会返回一个有序列表
  • 终须遍历二茬搜索树,用递归解法会自动调用栈,非递归也需要用栈来作为辅助数据结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ry tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
# @param root, a tree node
# @return a tree node
def inorder(self, root, list, listp):
if root:
self.inorder(root.left, list, listp)
list.append(root.val); listp.append(root)
self.inorder(root.right, list, listp)
def recoverTree(self, root):
list = []; listp = []
self.inorder(root, list, listp)
list.sort()
for i in range(len(list)):
listp[i].val = list[i]
return root

将数字排序,然后inorder节点,将节点的val变成数字。简单暴力

空间复杂度为O(1)解法

以下代码为专门来测试上面文章中的例子,看下具体是如何运行的。
题目有一个附加要求就是要求空间复杂度为常数空间。而算法一的空间复杂度为O(N),还不够省空间。以下的解法也是中序遍历的写法,只是非常巧妙,使用了一个prev指针。例如一颗被破坏的二叉查找树如下:

1
2
3
4
5
6
7
8
9

        4

       / \
      2 6

/ \ / \

1 5 3 7

很明显3和5颠倒了。那么在中序遍历时:当碰到第一个逆序时:为5->4,那么将n1指向5,n2指向4,注意,此时n1已经确定下来了。然后prev和root一直向后遍历,直到碰到第二个逆序时:4->3,此时将n2指向3,那么n1和n2都已经确定,只需要交换节点的值即可。prev指针用来比较中序遍历中相邻两个值的大小关系,很巧妙。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#!/usr/bin/python
#coding:utf-8

prev = None
n1 = None
n2 = None


class Node:
def __init__(self ,val ,left, right):
self.val = val
self.left = left
self.right = right
def __str__(self):
return str(self.val)

node1 = Node(1, None, None)
node5 = Node(5, None, None)
node2 = Node(2, node1, node5)
node3 = Node(3, None, None)
node7 = Node(7, None, None)
node6 = Node(6, node3, node7)
node4 = Node(4, node2, node6)



class Solution:
# @param root, a tree node
# @return a tree node
prev = None # 上一个根
n1 = None
n2 = None
def FindTwoNodes(self, root):
if root:
print "enumerate" + str(root) + " prev="+ str(self.prev) + " root=" + str(root)
self.FindTwoNodes(root.left)
# 因为是bst的inorder traversal,理论上prev肯定会大于当前的节点,所以这里就发现了第一个顺序有误的地方
if self.prev and self.prev.val > root.val:
print "first called prev is "+ str(self.prev) + " root is " + str(root)
self.n2 = root
if self.n1 == None:
print "second called"
self.n1 = self.prev
self.prev = root
self.FindTwoNodes(root.right)

def recoverTree(self, root):
self.n1 = self.n2 = None
self.prev = None
self.FindTwoNodes(root)
self.n1.val, self.n2.val = self.n2.val, self.n1.val
return root

s = Solution()
s.FindTwoNodes(node4)
print s.n1.val, s.n2.val

输出结果为

1
2
3
4
5
6
7
8
9
10
11
enumerate4 prev=None  root=4
enumerate2 prev=None root=2
enumerate1 prev=None root=1
enumerate5 prev=2 root=5
first called prev is 5 root is 4
second called
enumerate6 prev=4 root=6
enumerate3 prev=4 root=3
first called prev is 4 root is 3
enumerate7 prev=6 root=7
5 3