魑魅搏人应见惯
总输他
覆雨翻云手
C++，二叉树的中序遍历。
中序的下一个结点只有三种情况：
- 右子树的最左结点
- 父节点中左儿子也是当前节点父节点的结点（就是这么绕。。。）
- 空结点
根据如上结论，就能写出代码了：
/*
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) return nullptr;
if (pNode->right) return inorder(pNode->right);
else if (pNode->next) {
while (pNode->next && pNode->next->left != pNode) pNode = pNode->next;
return pNode->next;
} else return nullptr;
}
TreeLinkNode *inorder(TreeLinkNode* pNode) {
if (pNode->left) return inorder(pNode->left);
else return pNode;
}
};
