1. Morris Traversal 二叉树遍历
Morris Traversal 可以实现不用栈、非递归地遍历二叉树，使用O(1)的空间复杂度遍历一颗二叉树，保证时间复杂度也是O(N)。
二叉搜索树中的众数
- Morris 中序遍历
- 如果当前节点没有左子树，则输出当前节点，然后跳转到当前节点的右子树上；
- 如果当前节点有左子树，那么当前节点的前驱节点一定在左子树的上，只要在左子树一直往右走就可以找到；
- 如果前驱节点没有右子树，那么将前驱节点的 right 指针指向当前节点（这是为了遍历完前驱节点之后可以找到当前节点）
- 如果前驱节点的右子树是当前节点，那么说明前驱节点已经被遍历过，而且被修改了 right 指针，这时可以将前驱节点的 right 指针置为 nullptr，然后遍历当前节点，跳转到当前节点的右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void morris_inorder_traversal(TreeNode *root) {
while ( cur ) {
if ( !cur->left ) {
std::cout << cur->val << ' ';
cur = cur->right;
}
else {
pre = cur->left;
while ( pre->right && pre->right != cur ) pre = pre->right;
if ( !pre->right ) {
pre->right = cur;
cur = cur->left;
}
else {
pre->right = nullptr;
std::cout << cur->val << ' ';
cur = cur->right;
}
}
}
}
|
2. Y型链表找公共相交节点
两个链表的第一个公共节点
描述：一个Y型链表找到相交的节点，简单来说有三种方法：
- 最简单的方法：使用一个存储链表1，然后遍历链表2，检查是否有节点在链表1出现，空间复杂度O(N);
- 另外两个方法如下图：
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
|
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int count1 = 0, count2 = 0;
ListNode *cur1 = headA, *cur2 = headB;
while ( cur1 ) {
++count1;
cur1 = cur1->next;
}
while ( cur2 ) {
++count2;
cur2 = cur2->next;
}
if ( count1 > count2 ) {
cur1 = headA;
cur2 = headB;
} else {
cur1 = headB;
cur2 = headA;
}
int difference = count1 > count2 ? count1 - count2 : count2 - count1;
while ( difference ) {
cur1 = cur1->next;
--difference;
}
while ( cur1 && cur2 ) {
if ( cur1 == cur2 ) return cur1;
cur1 = cur1->next;
cur2 = cur2->next;
}
return nullptr;
}
};
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *cur1 = headA, *cur2 = headB;
while ( cur1 != cur2 ) {
cur1 = cur1 ? cur1->next : headB;
cur2 = cur2 ? cur2->next : headA;
}
return cur1;
}
};
|