面试题8: 二叉树的下一个节点

package cn.zxy.interview;

import sun.reflect.generics.tree.Tree;

/**
 * 分析:
 * 要求: 给出二叉树和其中一个节点, 找出该节点x在中序遍历序列中的下一个节点
 *
 * 1. x有右子树 --> 找到右子树的最左节点 (ps如果右子树是斜右子树, 那么该子树的根节点就是最左节点)
 * 2. x无右子树 -- > x是其父节点的左孩子, 其父节点就是下一个节点
 *                  x是其父节点的右孩子, 往上(根据指向父节点的指针)找到这样一个节点y, y节点是其父节点的左孩子, 这个父节点就是下一个节点
 *
 */

// 注: 外部类可以直接访问内部类私有成员变量
public class A08_BinaryTreeNextNode {
    private static class TreeNode{
        private int value;
        private TreeNode parent;
        private TreeNode lchild;
        private TreeNode rchild;
    }

    public static TreeNode binaryTreeNextNode(TreeNode p){
        if(p == null) return null;

        TreeNode pNext = null;
        if(p.rchild != null){
            // 引用指向右子树根节点
            TreeNode pRight = p.rchild;
            while (pRight.lchild != null){
                // 如果该节点还有左孩子, 就指向左孩子, 直到没有左孩子, 这个节点就是了
                pRight = pRight.lchild;
            }
            pNext = pRight;
        }
        // 因为下面这两种情况都是从父节点中找, 因此先判断是否有父节点;
        // 如果没有, 那么该节点就是根节点, 没有右节点, 又是根节点
        // 这个节点就是中序遍历的最后一个节点, 没有下一个节点了
        else if(p.parent != null){
            TreeNode pCurrent = p;
            TreeNode pParent = p.parent;

            // 往上找, 如果找到某个节点pCurrent是其父节点的左节点则退出
            while(pParent != null && pCurrent == pParent.rchild){
                pCurrent = pParent;
                pParent = pParent.parent;
            }
            pNext = pParent;
        }
        return pNext;
    }

}