剑指offer系列46：二叉树的下一个结点

寻找中序遍历中的给定结点的下一个结点，可以分为以下几种情况。

1.该节点有右子树，其右子树没有左结点，那么下一个一定就是右子树

2.该节点有右子树，其右子树有左结点，那么下一个一定就是右子树的左结点

3.没有右子树，有父节点，该节点是父节点的左子树，那么下一个就是它的父节点

4.没有右子树，有父节点，该节点是父节点的右子树，就要一直往上找，直到找到其中一个父结点是其自身的父节点的左子树。

5.没有右子树，也没有父节点，下一个是空。

做这个题目的时候要把这几种情况都考虑到。记住中序遍历的顺序：左->根->右。

因此这个题目可以分为两大类，有右子树就去右子树里面找右子树的左子树，没有右子树就去找它的一个父节点是其自己父节点的左子树，因为必须是左子树才能有下一个结点，右子树是没有下一个结点的。

 1 class Solution {
 2 public:
 3     TreeLinkNode* GetNext(TreeLinkNode* pNode)
 4     {
 5         if (pNode == NULL)
 6             return NULL;
 7         TreeLinkNode* pnext = NULL;
 8         if (pNode->right)//首先找它的右子树
 9         {
10             TreeLinkNode* pright = pNode->right;
11             while (pright->left)
12             {
13                 pright = pright->left;
14             }
15             pnext = pright;
16         }
17         else {
18             if (pNode->next)//没有右子树就找父节点
19             {
20                 TreeLinkNode* parent = pNode->next;
21                 TreeLinkNode* cur = pNode;
22                 while (cur != parent->left&&parent->next)
23                 {
24                     cur = parent;
25                     parent = parent->next;
26                 }
27                 if(cur == parent->left)//找到的结点必须是其父节点的左子树
28                      pnext = parent;
29                 else
30                 {
31                     return NULL;//最后一个右子树就返回空
32                 }
33                 
34             }
35         }
36     
37         return pnext;
38 
39     }
40 };