二叉树的下一个节点

1.题目：
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
2.思路：
方法一：暴力解法

根据给出的结点求出整棵树的根节点
根据根节点递归求出树的中序遍历，存入vector
在vector中查找当前结点，则当前结点的下一结点即为所求。 

虽然有点暴力，但是时间复杂度也是线性的，第一步：最坏为O(N), N为整棵树结点的个数。第二步：O(N), 第三步：最坏为O(N),
所以整的时间复杂度：3*O(N)

import java.util.ArrayList;
public class Solution {
   ArrayList<TreeLinkNode> list=new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        //1.找到根节点
        TreeLinkNode root=pNode;
        while(root.next!=null){
            root=root.next;
        }
        //2.中序遍历，结果存入ArrayList数组中
        inOrder(root);
        //3.遍历输出结果
        for(int i=0;i<list.size();i++){
            if(pNode==list.get(i)){
                return i==list.size()-1?null:list.get(i+1);
            }
        }
        return null;
    }
    public void inOrder(TreeLinkNode root){
        if(root.left!=null){
            inOrder(root.left);
        }
          list.add(root);
        if(root.right!=null){
            inOrder(root.right);
        }
    }
}

方法二：不去遍历，寻找下一节点的特性
根据中序遍历的规则，下一节点要么是左子树，要那么是父节点

仔细观察，可以把中序下一结点归为几种类型：

有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H

无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E

无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode==null){
            return null;
        }
        //1.当前节点有右子树，则去递归寻找左子树
        if(pNode.right!=null){
            pNode=pNode.right;
            while(pNode.left!=null){
                pNode=pNode.left;
            }
            return pNode;
        }
        //2.当前节点无右子树，且有父节点
        while(pNode.next!=null){
            //2.1当前节点为父节点的左子树
            if(pNode.next.left==pNode){
                return pNode.next;
            }
            //2.2当前节点为父节点的右子树，则继续往上找
            pNode=pNode.next;
        }
        //3.既无右子树也父节点，即根节点返回null
        return null;
    }
}