二叉树的下一个结点

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

思路：

• 给出了其中一个节点，通过next方法找到根节点；

• 中序遍历，将遍历结果加入集合中；

• 从集合中找到给定节点位置i，返回i+1位置的节点；

  import java.util.ArrayList;
  public class Solution {
  ArrayList<TreeLinkNode> list = new ArrayList<>();
  public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode == null) return null;
    TreeLinkNode fNode = pNode;
    // 找到根节点，根节点没有父节点
     while (fNode.next != null){
        fNode = fNode.next;
    }
    midSort(fNode);
  
    int len = list.size();
    for (int i = 0; i < len; i++) {
        if (pNode == list.get(i)){
            return i == len-1? null: list.get(i+1);
        }
    }
  
    return null;
  }
  // 中序遍历
  public void midSort(TreeLinkNode pNode){
  
    if (pNode != null){
        midSort(pNode.left);
        list.add(pNode);
        midSort(pNode.right);
    }
  }
  }