剑指offer 二叉树的下一个结点

迈不过友情╰ 2021-10-14 03:40 313阅读 0赞

# [剑指offer题型分类及各题的代码及解题思路][offer] #

## 题目描述 ##

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

初始结构定义如下：

/\*  
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)  
    \{\}  
\};

思路：首先知道中序遍历的规则是：左根右，然后作图

![aHR0cHM6Ly91cGxvYWRmaWxlcy5ub3djb2Rlci5jb20vZmlsZXMvMjAxNzEyMjUvNzczMjYyXzE1MTQxOTgwNzUxMDlfMjAxNTExMDQyMzQwMzQyNTE][]

结合图，我们可发现分成两大类：1、有右子树的，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G） 2、没有右子树的，也可以分成两类，a)是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ； b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有eg：M，那么他就是尾节点。

分析二叉树的下一个节点，一共有以下情况：

1.二叉树为空，则返回空；

2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；

3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。

C++实现代码如下：

TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
    	if(pNode==NULL)
    		return NULL;
    	if(pNode->right!=NULL)
    	{
    		pNode=pNode->right;
    		while(pNode->left!=NULL)
    			pNode=pNode->left;
    		return pNode;
    	}  
    	while(pNode->next!=NULL)
    	{
    		TreeLinkNode *proot=pNode->next;
    		if(proot->left==pNode)
    			return proot;
    		pNode=pNode->next;
    	}
    	return NULL;
    }

[offer]: https://blog.csdn.net/qq_26079093/article/details/96605538
[aHR0cHM6Ly91cGxvYWRmaWxlcy5ub3djb2Rlci5jb20vZmlsZXMvMjAxNzEyMjUvNzczMjYyXzE1MTQxOTgwNzUxMDlfMjAxNTExMDQyMzQwMzQyNTE]: /images/20211013/8234274bfea34ce5b2cad8b413bdb155.png