剑指OfferJZ57：二叉树的下一个节点-java版

5

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

中序遍历：左中右

寻找当前节点（pNode）的下一个节点,主要分三种情况：

第一种情况，当前节点右孩子不为空 如：节点2 它的下一个节点是它的右孩子6 （右孩子下没有孩子） 如：节点3 它的下一个节点是它的右孩子8 （右孩子下没有孩子） 如：节点1 它的下一个节点是它的右孩子3，但右孩子下也有孩子，那么最终节点1的下一个节点就取其右孩子的左孩子7

第二种情况，当前节点右孩子为空，并且当前节点是父亲节点的左孩子 如：节点5 它的下一个节点是它的父节点2

第三种情况，当前节点右孩子为空，并且当前节点是父亲节点的右孩子 如：节点6 它的下一个节点是它的父节点的父节点1

注意：当当前节点为最后一个节点时，它的下一个节点为空，题中需要对这种情况进行判断

 public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //pNode当前节点
        if(pNode.right!=null){
            //第一种情况，pNode节点的右孩子不为空
            pNode=pNode.right;
            while(pNode.left!=null){//pNode节点的右孩子的左孩子也不为空时
                pNode=pNode.left;
            }
            return pNode;
        }else{
            //tempNode当前节点的父亲结点
            TreeLinkNode tempNode=pNode.next;
            if(tempNode==null){//当前节点为根节点（根节点的父节点tempNode为null）
                return null;
            }
            if(tempNode.left==pNode){
                //第二种情况，当前节点右孩子为空，并且当前节点是父亲节点的左孩子，那么当前节点pNode的下一个节点是它的父节点
                return tempNode;
            }else{
                //第三种情况，当前节点右孩子为空，并且当前节点是父亲节点的右孩子,那么当前节点pNode的下一个节点是它的父节点的父节点
                //flag=false标记当前节点为最后一个节点（最后一个节点的下一个节点为null）
                boolean flag=false;
                while(tempNode.next!=null){
                    if(tempNode.next.left==tempNode){
                        flag=true;//当前节点非最后一个节点
                        break;
                    }
                    tempNode=tempNode.next;
                }
                //flag为true时，说明pNode所指的节点不是二叉树中最后一个节点
                //tempNode.next当前节点父节点的父节点
                return flag ? tempNode.next: null;
            }
        }

    }
}
class TreeLinkNode{
    int val;
    TreeLinkNode left=null;
    TreeLinkNode right=null;
    TreeLinkNode next=null;

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