题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解题思路
中序遍历二叉树：先左树–>根结点–>右树。
遍历顺序为：GDHBAEICF.
- 若当前结点，有右子树树，则当前结点的下一个就是右子树的中序遍历的第一个结点。
- 若当前结点，无右子树，但是他是双亲结点的左结点，则当前结点的下一个结点就是双亲结点；
- 若当前结点，无右子树，且是双亲结点的右结点，则要一直返回到双亲结点，直到返回的双亲结点是某结点的左结点，停止。
代码
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
| 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* pCur = pNode;
TreeLinkNode* pPar = pNode->next;
while (pPar != NULL && pCur == pPar->right)
{
pCur = pPar;
pPar = pCur->next;
}
pNext = pPar;
}
return pNext;
}
};
|
参考博文链接：https://cuijiahua.com/blog/2018/01/basis_57.html