JZ57 二叉树的下一个结点

1 直接通过next返回父节点
2. 利用next信息分类讨论

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    //中序遍历 不是叶子节点 总是右子树的最左叶子节点
    // 是zuo叶子结点 返回父节点
    // 是you叶子结点，返回迭代查询 返回当前点的父节点的右孩子结点还没有被遍历的节点
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode.left == null && pNode.right==null){
            //是zuo叶子结点 返回父节点
            if(pNode.next!=null && pNode.next.left == pNode){
                return pNode.next;
            }
            // 是you叶子结点，返回迭代查询 
            // 返回当前点的父节点的右孩子结点还没有被遍历的节点
            if(pNode.next!=null && pNode.next.right == pNode){
                return chaxun(pNode);
            }
        }else{
            //不是叶子节点，右节点为空
            if(pNode.right == null) return pNode.next;
            //右节点不为空 转移到右孩子中的最左叶节点
            pNode = pNode.right;
            while(pNode.left!=null) pNode = pNode.left;
            return pNode;
        }
        return null;

    }
    public TreeLinkNode chaxun(TreeLinkNode pNode){
        // 到根节点 说明是 最右的叶子结点  返回空
        if(pNode.next == null) return null;
        // 当前节点不是 父节点的右子树 该父节点即是中序遍历要输出的值
        if(pNode.next.right != pNode) return pNode.next;
        // 返回父节点继续寻找  
        return chaxun(pNode.next);
    }
}