二叉树的下一个节点

二叉树的下一个节点

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

注意：

• 如果给定的节点是中序遍历序列的最后一个，则返回空节点;
• 二叉树一定不为空，且给定的节点一定不是空节点；

数据范围

树中节点数量 [0,100]。

样例

假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。

则应返回值等于3的节点。

解释：该二叉树的结构如下，2的后继节点是3。
  2
 / /
1   3

解题思路见注释：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode *father;
 8  *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 9  * };
10  */
11 class Solution {
12 public:
13     TreeNode* inorderSuccessor(TreeNode* p) {
14         if (p == nullptr) {
15             return nullptr;
16         }
17         TreeNode *pNext = nullptr;
18         // 如果当前节点的右节点不为空,则当前节点的下一个节点为当前节点的右节点的最左节点
19         if (p->right != nullptr) {
20             TreeNode *pRight = p->right;
21             while (pRight->left != nullptr) {
22                 pRight = pRight->left;
23             }
24             pNext = pRight;
25         } else if (p->father != nullptr) { // 当前结点无右子树，则需要找到一个是它父结点的左子树结点的结点 
26             // 当前节点
27             TreeNode *curNode = p;
28             // 当前节点的父节点
29             TreeNode *fatherP = p->father;
30             while (fatherP != nullptr && curNode == fatherP->right) {
31                 curNode = fatherP;
32                 fatherP = curNode->father;
33             }
34             pNext = fatherP;
35         }
36         return pNext;
37     }
38 };