题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解答
分情况判断
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
| public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode == null) {
return null;
}
if (pNode.right != null) {
TreeLinkNode tmp = pNode.right;
while (tmp.left != null) {
tmp = tmp.left;
}
return tmp;
} else {
if (pNode.next == null) {
return null;
} else if (pNode.next.left == pNode) {
return pNode.next;
} else {
TreeLinkNode tmp = pNode.next;
while (tmp.next.left != tmp) {
tmp = tmp.next;
if (tmp.next == null) {
return null;
}
}
return tmp.next;
}
}
}
|
官方题解
链接：https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e?answerType=1&f=discussion
来源：牛客网
题目描述：给你一颗二叉树的一个结点，返回中序遍历顺序中这个结点的下一结点。二叉树不仅有左右孩子指针，还有指向父亲结点的指针。
Q1：首先问你一个问题，如果这道题出现在笔试题中，你会用什么方法做？如果出现在面试题中呢？
A1：我想你肯定有点疑惑，同一道题为什么还分出现在笔试题中还是面试题中呢？很显然，笔试题中只要能过就好，设计的算法丑点，慢点也无所畏，不一定需要最优解法，当然前提是能够通过。而面试中就不一样了，显然面试官希望听到最优解法。
方法一：暴力解法
如果在笔试题中看到这道题，直接模拟题意就好了。题意需要找到某个结点中序遍历的下一个结点，那我们的做法很显然可以这样：
- 根据给出的结点求出整棵树的根节点
- 根据根节点递归求出树的中序遍历，存入vector
- 在vector中查找当前结点，则当前结点的下一结点即为所求。
虽然有点暴力，但是时间复杂度也是线性的，第一步：最坏为O(N), N为整棵树结点的个数。第二步：O(N), 第三步：最坏为O(N),
所以整的时间复杂度：3*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
| class Solution {
public:
void pre_order(TreeLinkNode *root, vector<TreeLinkNode*> &v) {
if (!root) {
return;
}
pre_order(root->left, v);
v.push_back(root);
pre_order(root->right, v);
}
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
TreeLinkNode *root = nullptr;
TreeLinkNode *tmp = pNode;
while (tmp) {
root = tmp;
tmp = tmp->next;
}
vector<TreeLinkNode*> v;
pre_order(root, v);
int n = v.size();
for (int i = 0; i < n; ++i) {
if (v[i] == pNode && i + 1 != n) {
return v[i+1];
}
}
return nullptr;
}
};
|
时间复杂度：O(N)
空间复杂度：O(N)
方法二：最优解法
但是，如果在面试中，方法一肯定上不了台面。但是最优解法该怎么去想呢？想不出来就画图分析，举个中序遍历的图：如下：
红色数字是中序遍历的顺序。接下来，我们就假设，如果当前结点分别是1,2 … 7，下一结点看有什么规律没？
1
2
3
4
5
6
7
| 1 => 2
2 => 3
3 => 4
4 => 5
5 => 6
6 => 7
7 => null
|
此时，可以总结一下：
[1] 是一类：特点：当前结点是父亲结点的左孩子
[2 3 6] 是一类，特点：当前结点右孩子结点，那么下一节点就是：右孩子结点的最左孩子结点,如果右孩子结点没有左孩子就是自己
[4 5]是一类，特点：当前结点为父亲结点的右孩子结点，本质还是[1]那一类
[7]是一类，特点：最尾结点
我写的可能不够清晰，但是，思想你要明白，当遇到不会的题，可以根据题意画图，分析，分析方法是关键。
代码如下：
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
| class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if (!pNode) {
return pNode;
}
if (pNode->right) {
pNode = pNode->right;
while (pNode->left) {
pNode = pNode->left;
}
return pNode;
}
while (pNode->next) {
TreeLinkNode *root = pNode->next;
if (root->left == pNode) {
return root;
}
pNode = pNode->next;
}
return nullptr;
}
};
|
时间复杂度：最坏情况下为O(N)
空间复杂度：O(1)