二叉树中找到一个节点的后继节点

二叉树中一个节点的后继节点指的是，二叉树的中序遍历的序列中的下一个节点。

class Solution {
 public:
  Node* getSuccessorNode(Node* node) {
    if (node == nullptr) return node;
    if (node->right != nullptr)
      return getLeftMost(node->right);
    else {
      Node* parent = node->parent;
      while (parent != nullptr && parent->right == node) {
        node = parent;
        parent = node->parent;
      }
      return parent;
    }
  };

 private:
  Node* getLeftMost(Node* node) {
    if (node == nullptr) return node;
    while (node->left != nullptr) node = node->left;
    return node;
  };
};