《剑指offer》刷题笔记(树):二叉树的下一个结点



题目描述

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

解题思路

如果一个结点有右子树,那么它的下一个结点就是它的右子树中的最左子结点;
如果给定结点是其父结点的左子结点,那么它的下一个结点就是它的父结点;
如果一个结点既没有右子树,并且它还是它父结点的右子结点,那我们就需要一直向上遍历,知道找到一个是其父结点的左子结点的结点。

对最后一种情况做下解释,比如我们为了找到下图中结点i的下一个结点,我们沿着指向父结点的指针向上遍历,先到达结点e。由于结点e是它父结点的b的右结点,我们继续遍历到b。b是其父结点a的左子结点,因此b的父结点a就是结点i的下一个结点。



C++版代码实现

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
/*
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)
{
if(pNode == NULL)
return NULL;

TreeLinkNode* pNext = NULL;
//当前结点有右子树,则下一结点是右子树的最左结点
if(pNode->right != NULL){
TreeLinkNode* pRight = pNode->right;
while(pRight->left != NULL)
pRight = pRight->left;
pNext = pRight;
}
//当前结点无右子树,则需要向上找到其父结点(可以是当前结点)可以作为左子树的时候
else if(pNode->next != NULL){
TreeLinkNode* pCurrent = pNode;
TreeLinkNode* pParrent = pNode->next;
while(pParrent != NULL && pCurrent == pParrent->right){
pCurrent = pParrent;
pParrent = pParrent->next;
}
pNext = pParrent;
}
return pNext;
}
};

系列教程持续发布中,欢迎订阅、关注、收藏、评论、点赞哦~~( ̄▽ ̄~)~

完的汪(∪。∪)。。。zzz

0%