JZ8 二叉树的下一个结点

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

1.根据给定的节点pNode找到二叉树的起始节点。

2.中序遍历起始节点，将遍历的结果存在ArrayList中。

3.将得到的ArrayList中取出pNode的下标，返回ArrayList中下标+1位置的节点即可。

import java.util.*;
public class Solution {
    public TreelinkNode GetNext(TreelinkNode pNode) {
        TreelinkNode temp = pNode;
        ArrayList list = new ArrayList<>();
        while(temp.next != null){
            temp = temp.next;
        }
        midshow(temp,list);
        int index = list.indexOf(pNode);
        if(index+1>=list.size()){
            return null;
        }
        return list.get(index+1);
    }
    public void midshow(TreelinkNode pNode,ArrayList list){
        if(pNode.left != null){
            midshow(pNode.left,list);
        }
        list.add(pNode);
        if(pNode.right != null){
            midshow(pNode.right,list);
        }
        
        
    }
}