剑指offer-二叉树的下一个节点

题目描述

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

解题思路

分情况考虑如下：

若该节点为空，则直接返回NULL；
若该节点有右子树，则它的下一个节点一定是右子树中最左边的叶子节点，所以从该节点右孩子开始循环，依次指向它的左孩子节点，直到左孩子节点为空停止，此时指针指向的节点即为目标节点；
若该节点无右子树，且该节点为它父节点的左孩子，那么中序遍历的下一个节点就是它的父节点；
若该节点无右子树，且该节点为它父节点的右孩子，此时可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。如果这样的节点存在，那么这个节点的父节点就是我们要找的下一个节点；
若以上情况都不满足，则该节点下一个节点为NULL。

代码

 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)
17             return NULL;
18         else if(pNode->right){
19             pNode=pNode->right;
20             while(pNode->left)
21                 pNode=pNode->left;
22             return pNode;
23         }
24         else if(pNode->next&&pNode==pNode->next->left)
25             return pNode->next;
26         else if(pNode->next&&pNode==pNode->next->right){
27             while(pNode->next&&pNode!=pNode->next->left)
28                 pNode=pNode->next;
29             return pNode->next;
30         }
31         else 
32             return NULL;
33     }
34 };