java-二叉树的下一个节点

题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解题思路
方法一：按照题意，分三步进行
1.找到根节点
2.进行中序遍历
3.找出下一节点
方法二：根据中序遍历的特点找规律

规律的结论：
如果该节点有右孩子节点，则下一节点为右孩子节点的最左孩子节点
否则
如果该节点是其父亲节点的左孩子节点，则下一节点为父亲节点
否则该节点是其父亲节点的右孩子节点则判断其父亲节点和再父亲节点的关系
如：5的父亲节点为2，但5是右孩子节点。所以判断2和6的关系，因为2是6的左孩子节点，所以结果是6。如果2是6的右孩子结点，则应再往上层走

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

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
//方法一：1.先找到根节点 2.进行中序遍历 3.找出下一节点
public class Solution {
    public void midorder(TreeLinkNode root,ArrayList<TreeLinkNode> list){
        if(root==null) return;
        midorder(root.left,list);
        list.add(root);
        midorder(root.right,list);
    }

    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        TreeLinkNode root=null;
        TreeLinkNode tmp=pNode;
        while(tmp != null){
            root=tmp;
            tmp=tmp.next;
        }
        ArrayList<TreeLinkNode> list=new ArrayList();
        midorder(root,list);
        for(int i=0;i<list.size();i++){
            if(list.get(i)==pNode && i+1 != list.size()){
                return list.get(i+1);
            }
        }
        return null;
    }
}
/*方法二：画图找规律
结论：如果该节点有右子树-则下一节点为右子树的最左下
如果该节点不是右子树，如果是父亲节点的左子树，则下一节点为父亲节点，否则为父亲节点的父亲节点
具体过程见offer官方题解*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode==null) return null;
        if(pNode.right !=null){
            pNode=pNode.right;
            while(pNode.left != null){
                pNode=pNode.left;
            }
            return pNode;
        }
        while(pNode.next !=  null){
            TreeLinkNode root=pNode.next;
            if(root.left==pNode){
                return root;
            }
            pNode=pNode.next;
        }
        return null;
    }
}