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

题目描述

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

思路：1、如果这个节点为空，那么返回空

2、如果这个节点有右孩子，那么这个节点的下一个节点是右子树的最左的叶子节点。

3、考虑这个节点不是根节点的情况（根节点的父亲节点是NULL），同时没有右孩子，那么判断这个节点是否是父亲节点的左孩子，如果是，返回其父亲节点，否则基于这个节点的父亲节点循环判断。

　　 4、当这个节点是根节点或者是右子树最右的叶子节点，下一个节点是NULL。

这里比较绕的是第三种情况，画图解释一下：

根据中序遍历，H的下一个节点是D，H是父亲节点的左孩子，那么直接返回其父亲节点。节点B也是如此。

我们来看节点I，I的下一个节点的B，我们首先访问到其父亲节点，发现I不是D的左孩子，那么我们就以其父亲节点D作为基节点，继续遍历父亲节点，发现D是父亲节点B的左孩子，那么返回B。

第四种情况：我们来看G节点，经过第三种情况循环遍历后，基节点会指向根节点，而根节点的父亲节点是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     //这里输入的是二叉树的某个节点指针。。。由于存在父节点的指针，所以不需要二叉树的根节点也可
15     TreeLinkNode* GetNext(TreeLinkNode* pNode)
16     {
17         //如果给的是空，那么返回空
18         if (pNode == NULL) {
19             return NULL;
20         }
21         //如果这个节点存在右子树，那么这个节点的下一个节点就是右子树的最左的叶子节点
22         if (pNode->right != NULL) {
23             pNode = pNode->right;
24             while (pNode->left != NULL) {
25                 pNode = pNode->left;
26             }
27             return pNode;
28         }
29         // 考虑这个节点属于一般节点（不是根节点，没有右子树），节点的下一个节点：如果这个节点是
30         // 父节点的左孩子，那么返回父节点，否则继续遍历。
31         while (pNode->next != NULL) {
32             TreeLinkNode *tmp = pNode->next;
33             if (tmp->left == pNode) {
34                 return tmp;
35             }
36             pNode = tmp;
37         }
38         return NULL; //考虑是根节点或者最右边的右叶子节点
39     }
40 };