这是《剑指Offer》的第八题 -- “二叉树的下一个节点”的记录。

题目：

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

思路：

我们可以把问题分为三种情况进行讨论：

  1. 如果给定的节点有右子树，根据中序遍历的顺序“左 -> 根 -> 右”，那么下一个节点一定是它右子树的 最左节点。
  2. 如果给定的节点没有右子树，且它是它父节点的左子节点，那么下一个节点就是它的父节点。
  3. 给定的节点没有右子树，且它是它父节点的右子节点，这种情况下，我们可以沿着指向父节点的指针 一直向上遍历，直到找到一个节点是它父节点的左子节点，那么这个节点的父节点就是下一个要遍历的节点。

因为这道题 Leetcode 中没有，所以我自己写一个程序来实现它。

以上。