剑指offer57：二叉树的下一个结点

1 题目描述

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

2 思路和方法

　　中序遍历，下一个结点有两种情况

　　a. 当前结点有右子树，就找出右子树中的最左的结点；

　　b. 当前结点没有右子树就往它的父节点找，找到第一个结点是它的父节点的左子节点的结点时停止，下一个结点就是该节点的父节点；

作如下表述：

（1）’：有右子树的，那么下个结点就是右子树最左边的点；

（2）’：没有右子树的，给出结点是父结点的左孩子，返回父结点；

（3）’：没有右子树，给出结点是父结点的右孩子，把给出结点的父节点作为下一个遍历的节点，向上回溯，直到当前结点是其父节点的左孩子时停止【直到找到一个父节点X，并且这个父节点X是其本身的父节点Y的左孩子为止】，下一个结点就是当前结点的父节点proot【return proot】。【TreeLinkNode *proot=pNode->next；proot->left==pNode，pNode是当前节点，pNode->next是当前节点的父节点，proot->left是其父结点的左结点】，

例子：　先序遍历：1 2 4 6 7 5 8 3（根左右）；　　中序遍历：6 4 7 2 5 8 1 3（左根右）【给出的结点为8，下一个结点为1为例】　　后序遍历：6 7 4 8 5 2 3 1（左右根）

3 C++核心代码

 1 /*
 2 struct TreeLinkNode {
 3     int val;
 4     struct TreeLinkNode *left;
 5     struct TreeLinkNode *right;
 6     struct TreeLinkNode *next;
 7     TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
 8         
 9     }
10 };
11 */
12 class Solution {
13 public:    
14     TreeLinkNode* GetNext(TreeLinkNode* pNode)
15     {
16         if(pNode==NULL)
17             return NULL;
18         if(pNode->right!=NULL)
19         {                                   
20             pNode=pNode->right;
21             while(pNode->left!=NULL)
22                 pNode=pNode->left;           //有右子树的，那么下个结点就是右子树最左边的点
23             return pNode;
24         } 
25         while(pNode->next!=NULL)
26         {                                        //pNode，是当前节点
27             TreeLinkNode *proot=pNode->next;     //proot，当前节点的父节点
28             if(proot->left==pNode)               //proot->left，当前节点的父节点的左结点
29                 return proot;
30             pNode=pNode->next;
31         }
32         return NULL;
33     }
34 };

View Code

参考资料

https://blog.csdn.net/langxue4516/article/details/82292216