本文为剑指 offer 系列第五十四篇。
主要知识点为二叉树，查找二叉树中序遍历给定节点的下一个节点。
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解题思路
对于给定的节点，
- 如果存在右子树，那么给定节点中序遍历的下一个节点就是右子树的最左侧节点。
- 如果不存在右子树，那么就可能存在两种情况，
- 当前节点是根节点的左子树，那么它中序遍历的下一个节点就是它的根节点。
- 当前节点是根节点的右子树，那么它中序遍历的下一个节点是当前所在左子树的根节点。
解题代码
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
| /*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
TreeLinkNode* res;
// 当前节点存在右子树
if(pNode && pNode->right){
TreeLinkNode* temp = pNode->right;
while(temp->left){
temp = temp->left;
}
res = temp;
}else{
// 当前节点不存在右子树，
TreeLinkNode* par = pNode->next;
while(pNode->next && par->right == pNode){
pNode = pNode->next;
par = pNode->next;
}
res = par;
}
return res;
}
};
|
时间复杂度为O(n),空间复杂度为O(1)
以上，本题结束！