《剑指offer》第七天：二叉树的下一个结点

❝某个办公室有个程序员猝死了。后来来了一个姑娘坐在猝死的程序员的位置，没人告诉她之前发生的事。有一天姑娘让男朋友远程帮忙改代码，自己去吃饭了。之后部门经理恰巧路过，看到电脑在自己写代码，第二天就辞职了。❞

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

对于结点 pNode：

• 如果它有右子树，则「右子树的最左结点」就是它的下一个结点；
• 如果它没有右子树，判断它与父结点 pNode.next 的位置情况：
  • 如果它是父结点的左孩子，那么父结点 pNode.next 就是它的下一个结点；
  • 如果它是父结点的右孩子，一直向上寻找，直到找到某个结点，它是它父结点的左孩子，那么该父结点就是 pNode 的下一个结点。

/*public class TreeLinkNode {    int val;    TreeLinkNode left = null;    TreeLinkNode right = null;    TreeLinkNode next = null;    TreeLinkNode(int val) {        this.val = val;    }}*/public class Solution {    /**     * 获取中序遍历结点的下一个结点     * @param pNode 某个结点     * @return pNode的下一个结点     */    public TreeLinkNode GetNext(TreeLinkNode pNode) {        if (pNode == null) {            return null;        }        if (pNode.right != null) {            TreeLinkNode t = pNode.right;            while (t.left != null) {                t = t.left;            }            return t;        }        // 须保证 pNode.next 不为空，否则会出现 NPE        if (pNode.next != null && pNode.next.left == pNode) {            return pNode.next;        }        while (pNode.next != null) {            if (pNode.next.left == pNode) {                return pNode.next;            }            pNode = pNode.next;        }        return null;    }}

1. 普通二叉树（完全二叉树；不完全二叉树）；
2. 特殊二叉树（所有结点都没有左/右子结点；只有一个结点的二叉树；二叉树的根结点为空）；
3. 不同位置的结点的下一个结点（下一个结点为当前结点的右子结点、右子树的最左子结点、父结点、跨层的父结点等；当前结点没有下一个结点）。
   我把我写的所有题解整理成了一本电子书放在了 github 上，三天内冲击到 github 排行榜榜首！近 5w 人下载阅读！要获取的话，直接进入下方链接就可以了（记得给我点个 star）：

https://github.com/geekxh/hello-algorithm