LeetCode的Easy题(二)

Description

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Follow up

Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Thinking

这个题是一个求众数的题目,对于一个排序好的数组来说,如果不用hash表来做的话,一个很容易想到的方法就是先遍历一次,将众数这个数出现的次数记录下来,然后第二次遍历的时候把相应的众数纪录下来就行。不过这里要注意到想要让BST能够按照一个排序数组遍历下来的话,需要中序遍历(一开始就没注意到这个问题……)

莫里斯遍历

在discuss区里面,我在被顶到第一名的回答中看到了“莫里斯遍历”这样一个新鲜词。

莫里斯遍历要解决的问题:
当在非栈型结构下遍历到二叉树的左儿子之后,不能很好地返回到父节点,并且也很难实现。莫里斯遍历使左儿子中的最大值的右儿子重新指向父节点,以实现回到父节点的步骤。

具体代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void inorder3(Node *root)//Morris中序遍历
{
Node *p = root;
while (p != NULL)
{
if (p->left == NULL)
printf("%d ", p->val), p = p->right;
else
{
Node *pre = p->left;
while (pre->right != NULL && pre->right != p)
pre = pre->right;
if (pre->right == NULL) //第一次访问,修改pre的右儿子
pre->right = p, p = p->left;
else //第二次访问,改回pre的右儿子
pre->right = NULL, printf("%d ", p->val), p = p->right;
}
}
}

大致示意图如下:

中序遍历示意图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void preorder3(Node *root)//Morris前序遍历
{
Node *p = root;
while (p != NULL)
{
if (p->left == NULL)
printf("%d ", p->val), p = p->right;
else
{
Node *pre = p->left;
while (pre->right != NULL && pre->right != p)
pre = pre->right;
if (pre->right == NULL) //第一次访问,修改pre的右儿子
pre->right = p, printf("%d ", p->val), p = p->left;
else //第二次访问,改回pre的右儿子
pre->right = NULL, p = p->right;
}
}
}

后序遍历要稍微复杂一些,存在一个翻转的问题。

1
2
3
4
5
6
7
8
9
10
11
12
void reverse(Node *p1, Node *p2)//使用right指针翻转p1到p2节点
{
if (p1 == p2) return;
Node *pre = p1, *p = p1->right;
while (true)
{
Node *tem = p->right;
p->right = pre;
if (p == p2) break;
pre = p, p = tem;
}
}
1
2
3
4
5
6
7
8
9
10
void print(Node *p1, Node *p2)//逆序打印p1到p2节点
{
reverse(p1, p2);
for (Node *p = p2; ; p = p->right)
{
printf("%d ", p->val);
if (p == p1) break;
}
reverse(p2, p1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void postorder3(Node *root)//Morris后序遍历
{
Node dummy(-1, root, NULL), *p = &dummy;
while (p != NULL)
{
if (p->left == NULL)
p = p->right;
else
{
Node *pre = p->left;
while (pre->right != NULL && pre->right != p)
pre = pre->right;
if (pre->right == NULL)
pre->right = p, p = p->left;
else
pre->right = NULL, print(p->left, pre), p = p->right;
}
}
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2018 Alex's Blog All Rights Reserved.

Yifeng Tang hält Urheberrechtsansprüche.