原创博文，转载请注明出处！
# 题目
父节点指向子节点的指针用实线表示，从子节点指向父节点的指针用虚线表示。
# 思路
- 如果节点有右子节点，则右子节点的最左节点是该节点的下一个节点。例如，寻找b的下一个节点的过程（b有右子节点e，e的左子节点是h，且h是e的最左节点，h是b的下一个节点）
- 如果节点无右子节点，但该节点是父节点的左子节点，则父节点是该节点的下一个节点。例如，寻找d的下一个节点的过程（d无右子节点，d是父节点b的左子节点，则b是de的下一个节点）
- 如果节点无右子节点，且该节点是父节点的右子节点，则沿着父节点的指针向上遍历。例如，寻找i的下一个节点的过程（i的父节点e，e是其父节点b的右子节点，节点b是其父节点a的左子节点，节点a是节点i的下一个节点）
# 代码
1 /* 2 struct TreeLinkNode { 3 int val; 4 struct TreeLinkNode *left; 5 struct TreeLinkNode *right; 6 struct TreeLinkNode *next; 7 TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) { 8 9 } 10 }; 11 */ 12 class Solution { 13 public: 14 TreeLinkNode* GetNext(TreeLinkNode* pNode) 15 { 16 // 特殊输入 17 if(pNode == nullptr) 18 return nullptr; 19 20 /* 寻找结果 */ 21 // 如果节点有右子节点，则右子节点的最左节点是该节点的下一个节点 22 // 如果节点无右子节点，但该节点是其父节点的左子节点，则父节点是该节点的下一个节点 23 // 如果节点无右子节点，且该节点是其父节点的右子节点，则沿着父节点向上遍历，满足XXX的父节点是其该节点的下一个节点 24 TreeLinkNode * res = nullptr; 25 if(pNode->right != nullptr) 26 { 27 TreeLinkNode* node_right = pNode->right; 28 while(node_right ->left != nullptr) 29 { 30 node_right = node_right->left; 31 } 32 res = node_right; 33 } 34 35 else if(pNode->next != nullptr) 36 { 37 // 当前节点和当前节点的父节点 38 TreeLinkNode * current = pNode; 39 TreeLinkNode * parent = pNode->next; 40 41 while(parent!=nullptr && current == parent->right) 42 { 43 current = parent; 44 parent = parent ->next; 45 } 46 47 res = parent; 48 } 49 return res; 50 } 51 }; # 复杂度
# 测试用例
- 空节点
- 特殊二叉树（只有一个节点的二叉树、只有左子节点的二叉树、只有右子节点的二叉树、完全二叉树和不完全二叉树）
- 不同位置的节点的下一个节点（下一个节点是当前节点右子节点、右子树的最左子节点、父节点、跨层父节点、无下一个节点）