二叉树的下一个节点

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

思路：

1. 若一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。

2. 若一个节点没有右子树，则向上不断遍历找第一个左子树中包含该节点的的节点

代码实现：

/**
 * 题目类型：二叉树
 *
 * 题目要求：给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？
 *  树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针
 *
 *  思路：1. 若一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。
 *       2. 若一个节点没有右子树，则向上不断遍历找第一个左子树中包含该节点的的节点
 */
public class GetNextNode {

    /**
     * 节点类
     */
    public static class TreeLinkNode {
        int value;
        TreeLinkNode left;
        TreeLinkNode right;
        TreeLinkNode next;

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

    /**
     * 找出中序遍历序列的下一个节点
     *
     * @param pNode 给定的节点
     * @return 返回给定节点的下一节点
     */
    private static TreeLinkNode getNext(TreeLinkNode pNode) {

        if (pNode == null)
            return null;

        if (pNode.right != null) {  // 右子树不为空
            TreeLinkNode pRight = pNode.right;
            while (pRight.left != null) {
                pRight = pRight.left;  // 下一节点为右子树的最左子节点
            }
            return pRight;
            // 右子树为空
        } else {
            while (pNode.next != null) {
                TreeLinkNode parent = pNode.next;
                if (parent.left == pNode) {
                    System.out.print("下一节点为：" + parent.value);
                    return parent;
                }
                pNode = pNode.next;
            }
        }

        return null;
    }
}