给定一棵二叉树和其中的一个节点，找出中序遍历序列的下一个节点。注意，树中的节点除了有两个分别指向左右子节点的指针，还有一个指向父节点的指针。
示例：
a / \ b c / \ / \ d e f g / \ h i 中序遍历序列：[d, b, h, e, i, a, f, c, g]题目中没有明确寻找中序遍历系列中哪一个节点的下一个节点，其实就是隐含了随便给一个序列中的点，都要求出下一个节点。这种情况下就必须挖掘中序遍历序列的整体规律，显然这种规律也不太好找，那么就来对序列中的点进行分类，根据这一点属于哪一类，对应那种处理方法，这就是一条比较清晰的思路。
剑指书中给出了一种点分类的方法，将二叉树中的点分成了三类：（1）该节点有右子树 （2）该节点无右子树 & 是本节点的父节点的左子节点（有点绕口，对比理解就是“我是我爸的第一个儿子”） （3）该节点无右子树 & 是本节点的父节点的右子节点。
下面分析这三类分别对应什么处理方法：
对于（1)，如果当前节点pNode具有右子树，则下一节点pNext就是从右子树的顶点开始，一直取左子节点，取到最后（取到的节点没有左子节点为止）的这个节点就是下一节点。对应示例中的b、c节点，b节点的下一节点是右子树的顶点e，接着取e的左子节点h，h没有左子节点了，那么h就是b的下一节点。同理，c的右子树顶点是g，g没有左子节点，因此g就是c的下一节点。很明显，（1）这里面，关键节点就是右子树的顶点与右子树最左末端节点。对于（2），当前节点pNode没有右子树，且是它父节点的左子节点，那么下一节点就是他的父节点。比如示例中的d，下一节点是b；h的下一节点是e；f的下一节点是c。对于（3），当前节点pNode没有右子树，且是它父节点的右子节点。这就要沿着父节点的指针向上回溯，一直找到某个节点是父节点的左子节点，则下一节点就是找到的这个节点的父节点。之所以要回溯的原因就是，当pNode到了（3）这种位置，比如示例中的i与g，都是当前子树的最右下方节点，根据中序遍历的顺序（左–根--右），只要到了i或g的位置了，那么他们对应的这一个子树就完全遍历完了，必须要找到根节点（如果示例中的树有五层的话，就要找到二级根节点），换一棵子树继续查找；或者直接结束查找（此时就是g的位置，整个二叉树最右下方的点，标志整个树都被遍历完了） struct BinaryTreeNode { int val; BinaryTreeNode *m_pLeft; BinaryTreeNode *m_pRight; BinaryTreeNode *m_pParent; }; BinaryTreeNode* GetNext(BinaryTreeNode *pNode) { if (pNode == nullptr) return nullptr; BinaryTreeNode *pNext = nullptr; // 1、当前节点有右子树，下一节点为 从右子树顶的节点开始不断取左子节点，取到最后（没有左子节点）就是 if (pNode->m_pRight != nullptr) { BinaryTreeNode *pRight = pNode->m_pRight; while (pRight->m_pLeft != nullptr) pRight = pRight->m_pLeft; pNext = pRight; } // 2、当前节点没有右子树，分成：(a)当前节点是它父节点的左子节点，下一节点是它的父节点 // (b)当前节点是它父节点的右子节点，下一节点要沿着父节点的指针往回遍历，直到找到一个是它父节点的左子节点的节点，下一节点是该节点的父节点 else if (pNode->m_pParent != nullptr) { BinaryTreeNode *pCurrent = pNode; BinaryTreeNode *pParent = pNode->m_pParent; while (pParent != nullptr && pCurrent == pParent->m_pRight) //(b) { pCurrent = pParent; pParent = pParent->m_pParent; } pNext = pParent; // (a) } return pNext; }这一题收获到的就是怎么审题，抓住问题的宾语，题目要 求什么。如果这个宾语范围很大，能不能以分类的形式分别解决这个宾语在不同情况时的问题。
