面试题8：二叉树的下一个节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
重点搞清楚思路：根据中序序列 左中右 考虑，指定节点下一个节点与右子树节点密切相关。
若节点有右子树，则下一个节点即为该右子树的最左节点；
若节点无右子树但有父节点，则沿着父节点一直向上遍历，直到找到一个节点，它是其父节点的左子节点；
若不满足以上两种情况，则无下一个节点。
代码：TreeLinkNode* GetNext(TreeLinkNode* pNode) { if (pNode == nullptr) return NULL; //若节点有右子树，则下一个节点是其右子树的最左侧节点 if (pNode->right) { TreeLinkNode* leftNode = pNode->right; while (leftNode->left) { leftNode = leftNode->left; } return leftNode; } //若节点没有右子树且有父节点 else if(pNode->next!=nullptr) { TreeLinkNode* parentNode = pNode->next; //若节点是其父节点的左子节点，则下一个节点为其父节点 if (pNode == parentNode->left) { return parentNode; } //若节点是其父节点的右子节点，这种情况就比较麻烦。我们沿着指向父节点的指针一直向上，一直找到一个节点是其父节点的左子节点，其父节点就是我们要找的节点 else { while (parentNode!=nullptr&& parentNode->next!=nullptr&&parentNode!=parentNode->next->left) { parentNode = parentNode->next; } return parentNode->next; } } //若节点无右子树且无父节点 else return nullptr; }
以前的代码：
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode==nullptr)
return NULL;
TreeLinkNode *node=nullptr;
//若节点有右子树，则下一个节点是右子树最左节点
if(pNode->right!=nullptr)
{
node=pNode->right;
while(node->left!=nullptr)
{
node=node->left;
}
}
//若节点没有右子树，则从其父节点入手
else if(pNode->next!=nullptr)
{
node=pNode;
TreeLinkNode *pNode_parent=pNode->next;
while(pNode_parent!=nullptr&&pNode_parent->left!=node)
{
node=pNode_parent;
pNode_parent=pNode_parent->next;
}
node=pNode_parent;
}
else
node=nullptr;
return node;
}
};
