/* 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* res = NULL; // case1: 节点存在右子树,则res是右子树的最左节点 if (pNode->right) { TreeLinkNode* tmp = pNode->right; while (tmp->left) { tmp = tmp->left; } return tmp; } // case2: 节点没有右子树,且当前节点是父亲节点的左子树,则父亲节点就是res // 注意加入pNode->next不为null的条件 else if (pNode->next && pNode->next->left == pNode) { return pNode->next; } // case3:节点没有右子树,且当前节点是父亲节点的右子树,则需要向上查找,知道迭代节点是父亲节点的左孩子停止 // 注意加入pNode->next不为null的条件 else if (pNode->right == NULL && pNode->next && pNode->next->right == pNode) { TreeLinkNode* pfather = pNode->next; while (pfather->next && pfather->next->right == pfather) { pfather = pfather->next; } return pfather->next; } return NULL; } };