剑指Offer第8题——二叉树的下一个节点

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

private class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        // next指向父结点
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }

首先明确思路：中序遍历规则：左根右

虚线为中序遍历下一个节点

总结：总体分成两种情况：

1. 节点有右子树的：下一个节点指的是该节点右子树最左边的点。（eg：D，B，E，A，C，G）
2. 节点无右子树的，又分两种情况：
   1. 没有右子树且该节点是父节点的左孩子（eg：N，I，L）那么父节点为该节点的下一个节点。
   2. 没有右子树且该节点是父节点的右孩子（eg：H，J，K，M），那么迭代找该节点的父节点。直到当前节点是其父节点的左孩子。那么左孩子的父节点为下一节点。如果迭代到顶端依然没有左孩子的情况，则为尾节点。eg：M。

    public TreeLinkNode getNext(TreeLinkNode pNode) {
        // 如果该节点的的右子树不为空
        if (pNode.right != null) {
            pNode = pNode.right;
            while (pNode.left != null) {
                pNode = pNode.left;
            }
            return pNode;
        }
        // 如果右子树为空，则找其父节点，当父节点的右子树为该节点时，继续向上找
        while (pNode.next != null && pNode.next.right == pNode) {
            pNode = pNode.next;
        }
        return pNode.next;
    }