Morris遍历是一种神级遍历方式，遍历一颗树做到时间复杂度$O(n)$ 空间复杂度是$O(1)$。基础的思路就是利用叶节点下面的空节点作为返回上级的指针。
基本思路：
- 当前节点cur
- 如果cur没有左孩子，那么直接滑向右孩子
- 如果cur有左孩子， 那么左孩子最右边的节点mostRight
- 如果mostRight.right指向，nil让其指向cur， cur 向左移动
- 如果mostRight.right指向cur，让mostRight指向nil， cur向右移动
Morris遍历， Python实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| def morrisIn(root):
if not root: return
cur = root
while cur:
if cur.left:
mostRight = cur.left
while mostRight.right and mostRight.right != cur:
mostRight = mostRight.right
if mostRight.right:
print(cur.val, end=" ")
mostRight.right = None
cur = cur.right
else:
mostRight.right = cur
cur = cur.left
else:
print(cur.val, end=" ")
cur = cur.right
|
创建树节点
1
2
3
4
5
| class Node:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
|
创建一颗平衡树
1
2
3
4
5
6
7
| def buildTree(nums):
if nums == []: return
mid = len(nums) >> 1
root = Node(nums[mid])
root.left = buildTree(nums[:mid])
root.right = buildTree(nums[mid+1:])
return root
|
1
| root = buildTree(list(range(10)))
|
显示树结构
1
2
3
4
5
6
7
8
9
10
11
12
| def prettyPrintTree(node, prefix="", isLeft=True):
if not node:
print("Empty Tree")
return
if node.right:
prettyPrintTree(node.right, prefix + ("│ " if isLeft else " "), False)
print(prefix + ("└── " if isLeft else "┌── ") + str(node.val))
if node.left:
prettyPrintTree(node.left, prefix + (" " if isLeft else "│ "), True)
|
│ ┌── 9
│ ┌── 8
│ │ └── 7
│ │ └── 6
└── 5
│ ┌── 4
│ │ └── 3
└── 2
└── 1
└── 0
0 1 2 3 4 5 6 7 8 9
先序和中序只是打印的地方不同：