面试题8（二叉树的下一个节点）剑指offer

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
考察点：二叉树中的中序遍历理解，画出结构，多情况分析，找到规律。
思路：分三种情况寻找下一个节点，分别是当前节点有右子树，当前节点无右子树并且是父节点的左孩子，当前节点无右子树并且是父节点的右孩子。根据中序遍历的查找规律，去进行节点替换。

struct TreeLinkNode { int val; struct TreeLinkNode* left; //左孩子 struct TreeLinkNode* right; //右孩子 struct TreeLinkNode* next; //父节点 TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { } }; class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { if (pNode == NULL) return NULL; TreeLinkNode* pNext = NULL; //总体上可以分为三种情况讨论 if (pNode->right != NULL) //如果右子树不为空，则是一直往右子树的左孩子找 { TreeLinkNode* pRight = pNode->right; while (pRight->left != NULL) { pRight = pRight->left; //一直往左找 } pNext = pRight; } else if (pNode->next != NULL) //若果右子树为空，就开始往父节点找 { TreeLinkNode* pCurrent = pNode; TreeLinkNode* pParent = pNode->next; //记录当前节点和父节点 //没到根节点和当前节点一直是父节点的右孩子，就一直往上找 while (pParent != NULL && pCurrent == pParent->right) { pCurrent = pParent; pParent = pCurrent->next; } //找到父节点是当前节点的左孩子的情况，赋值 pNext = pParent; } return pNext; } };

【面试题8（二叉树的下一个节点）】