剑指offer---二叉树的下一个结点 

题目描述

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

解题思路

解题思路（分三种情况）：

中序遍历{d,b,h,e,i,a,f,c,g}

1. 如果当前结点有右子树
下一个节点就是它的右子树的最左子节点（从右子节点出发一致沿着指向左子节点的指针，即可找到）
如：b ——》h, a——》f

2. 如果当前节点没有右子树
（1） 如果当前节点是它父节点的左子节点
下一个节点就是它的父节点
如：d——》b, f——》c, h——》e

（2）如果当前节点是它父节点的右子节点
沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点，如果这样的节点存在，那么这个节点的父节点就是我们要找到的下一个节点
如：i节点的下一个节点：沿着指向父节点的指针向上遍历，先到e,e是b的右子节点，不是，继续向上遍历，到b, b是a的左子节点，因此节点b的父节点a就是i的下一个节点

如：g节点的下一个节点：沿着指向父节点的指针向上遍历，先到c, c是a的右子节点，不是，继续向上遍历到a, a是根节点，无父节点，因此g没有下一个节点。

代码

// 题目：给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？
// 树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。
 
public class NextNodeInBinaryTrees {
    private class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode parent = null;
 
        TreeLinkNode(int val) {
            this.val = val;
        }
    }
 
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            System.out.print("结点为null ");
            return null;
        }
        if (pNode.right != null) {
            pNode = pNode.right;
            while(pNode.left!=null)
                pNode=pNode.left;
            return pNode;
        }
        while(pNode.parent !=null){
            if(pNode==pNode.parent .left)
                return pNode.parent;
            pNode=pNode.parent;
        }
        return null;
    }