二叉树的下一个结点 ​

题目： ​

给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父节点的指针。

思路： ​

这个问题我们可以分为三种情况来讨论。

第一种情况，当前节点含有右子树，这种情况下，中序遍历的下一个节点为该节点右子树的最左子节点。因此我们只要从右子节点出发，一直沿着左子节点的指针，就能找到下一个节点。

第二种情况是，当前节点不含有右子树，并且当前节点为父节点的左子节点，这种情况下中序遍历的下一个节点为当前节点的父节点。

第三种情况是，当前节点不含有右子树，并且当前节点为父节点的右子节点，这种情况下我们沿着父节点一直向上查找，直到找到一个节点，该节点为父节点的左子节点。这个左子节点的父节点就是中序遍历的下一个节点。