题解 | #二叉树的下一个结点#

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

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
首先要明白，next是结点的父指针。
然后先一直next搞到根节点，然后dfs（注意判定root不为空，否则直接返回）
再然后遍历list，找到pHead结点，然后判断，如果已经是中序遍历最后一个结点，返回NULL
如果不是，就返回它的下一个结点。
import java.util.*;
public class Solution {
    ArrayList<TreeLinkNode> a = new ArrayList<TreeLinkNode>();
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode root = pNode;//定义根节点
        while(root.next != null){
            root = root.next;//不断的向上循环直到root是根节点
        }
        dfs(root);
        for(int i = 0;i < a.size();i++){
            if(a.get(i).equals(pNode)){
                if(i != a.size()-1)
                    return a.get(i + 1);
                else return null;
            }
        }
        return null;
    }
    void dfs(TreeLinkNode root){//以递归方式实现“左根右“的中序遍历
        if(root == null)return;
        dfs(root.left);
        a.add(root);
        dfs(root.right);
    }
        
        
        
        
        
        
        
        
}