请找出二叉树的下一个节点

给定一棵二叉树的其中一个节点，请找出中序遍历的下一个节点.
注意：

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

样例

假定二叉树是：[2, 1, 3, null, null, null, null]，给出的是值等于2的节点。
则返回值等于3的节点。
解释：二叉树的结构如下，2的后继节点是3
   2
  / \
 1   3

题解

/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *    int val;
  *    TreeNode *left;
  *    TreeNode *right;
  *    TreeNode *father;
  *    TreeNode(int x): val(x), left(NULL), right(NULL) father(NULL) {}
  * };
  */
class Solution {
public:

  map<int, int> hash;
  vector<int> preorder, inorder;

  TreeNode* inorderSuccessor(TreeNode* p) {
    if (p->right) {
      p = p->right
      while(p->left) p = p->left;
      return p;
    }

    while ( p->father && p == p->father->right) p = p->father;
    return p->father;
  }
}

Solution

1. 如果当前节点有右子树，则右子树的最左的节点就是当前节点的后继。
2. 如果当前节点没有右子树，并且当前节点是它father的左节点，则它的father就是当前节点的后继。
3. 如果当前节点没有右子树，并且当前节点是它father的有节点，则它的某个父代节点A为节点A的父节点B的左节点时，节点B就是它的后继。
4. 这道题主要考察对树的中序遍历。