package com.exe7.offer;

 /**

  * 【题目】给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。

  *            注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

  * @author WGS

  *

  */

 public class GetNextNode {

     public class TreeNode{

         int val;

         TreeNode left=null;

         TreeNode right=null;

         TreeNode next=null;

         public TreeNode(int val){

             this.val=val;

         }

     }

     public TreeNode getNextNode(TreeNode pNode){

         if(pNode==null) return null;

         //1 判断有无右子树，有就是右子树最左子节点；

         TreeNode curNode=null;

         if(pNode.right!=null){

             curNode=pNode.right;

             while(curNode.left!=null){

                 curNode=curNode.left;

             }

             return curNode;

         }

         //2 无右子树;

         else{

             //1) 判断该结点是否是其父节点的左结点，是，下个结点就是其父节点。

             if(pNode.next==null) return null;

             if(pNode==pNode.next.left){

                 return pNode.next;//返回其父节点

             }

             //2) 该结点不是父节点的左结点即是其右节点，则判断其父节点是否是父父结点的左结点；

             curNode=pNode.next;//该结点的父节点

             while(curNode.next!=null){

                 if(curNode==curNode.next.left){

                     return curNode.next;//返回其父节点的父节点

                 }

                 curNode=curNode.next;//继续回溯

             }

         }    

         return null;

     }

 }