[剑指Offer] 57.二叉树的下一个结点

题目描述

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

 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         //如果有右子树，则返回右子树中最左侧的结点
19         if(pNode->right != NULL){
20             pNode = pNode->right;
21             while(pNode->left != NULL){
22                 pNode = pNode->left;
23             }
24             return pNode;
25         }
26         //如果没有右子树，则找到第一个当前结点是父结点左子树的结点，返回其父结点
27         while(pNode->next != NULL){
28             if(pNode->next->left == pNode)
29                 return pNode->next;
30             pNode = pNode->next;
31         }
32         //推到根仍未找到，则说明当前结点为遍历后的尾结点，返回空
33         return NULL;
34     }
35 };