Question

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

思路：中序遍历，寻找。

应先找到根节点。

import java.util.*;
public class Solution {
  List<TreeLinkNode> list = new ArrayList<>();
  public TreeLinkNode GetNext(TreeLinkNode pNode)
  {
    if(pNode == null) return null;
    TreeLinkNode root = pNode;
    while(root.next != null){
      root = root.next;
    }
    inorder(root);
    for(int i = 0; i < list.size()-1; i ++){
      if(list.get(i) == pNode) return list.get(i+1);
    }
    return null;
  }
  private void inorder(TreeLinkNode root){
    if(root == null) return;
    inorder(root.left);
    list.add(root);
    inorder(root.right);
  }
}