开始学算法（刷算法题）过程记录 7

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

题目链接：https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e

解题思路：找规律，分类讨论。

第一种情况：如果给定节点有右子树，按中序遍历规律，左中右，可以得知下一个节点就是他的右子树中的最左子节点。也就是给定节点是中，下一个节点是右，但右可能还有子树，左中右，继续沿着子树的左节点一直到最后一个为之。

也就是说：如果给定节点有右子树，那就从右子节点出发一直沿着指向左子节点的指针，我们就能找到给定节点的下一个节点。

例如，e的下一个是i。b的下一个是h，沿着b的右子节点e出发一直沿着指向左节点的指针找到h。

第二种情况：给定节点没有右子树，如果给定节点是左节点，那么下一个节点就是父节点，因为左中右遍历为序，给定节点为左那下一个中就是给定节点的父节点。例如d节点下一个是b节点。

第三种情况：给定节点没有右子树，并且它还是父节点的右节点。例如：i节点和g节点。我们可以沿着父节点一路向上，找到一个是父节点的左节点的节点，例如，i一路往上找，找到b是父节点a的左节点，如果有b节点存在，那a就是中序遍历中 i 节点的下一个节点。

找不到的话，说明他是最后一个节点，例如g节点，往上找不到一个是父节点的左节点的节点。

接下来就是把他们用ifelse组合一下

三种情况 有右子树 无右子树是父左 无右子树是父右