题解 | #二叉树的下一个结点# 中序找节点的下一个节点

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

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    List<TreeLinkNode> list = new ArrayList<>();
    /*
      解题思路：
      由于题目告诉你，树不仅有左右节点而且还有指向父节点的指针。
      并且题目参数传进来的是子树的根节点，要你按照中序遍历顺序，找到子树根节点的下一个节点
      
      所以！大致思路就是
          1）先通过参数节点，找到大树顶根。
          2）找到了大树顶根，就可以中序遍历，存储节点值。
          3）拿着参数节点去中序结果中找目标值相等的下一个节点即可。
      
    */ 
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode root = findParent(pNode);
        midShow(root);
        // 程序执行到此，list集合中按照中序遍历存储了元素
        return getNode(pNode);    
    }
    // 从中序结果中找到目标值的下一个元素
    public TreeLinkNode getNode(TreeLinkNode pNode){
        TreeLinkNode res=null;
        int size = list.size();
        for(int i=0;i<size;i++){
            TreeLinkNode node = list.get(i);
            if(node.val==pNode.val){
                if(i==size-1) return res;
                res = list.get(i+1);
                return res;
            }
        }
        // 程序能执行到此处，说明中序结果里面没有目标节点。
        return res;
    }
    
    // 中序遍历存储结果值.
    public void midShow(TreeLinkNode root){
        if(root.left!=null){
            midShow(root.left);
        }
        list.add(root);
        if(root.right!=null){
            midShow(root.right);
        }
    }
    
    // 找父节点。（找到大树的根节点）
    public TreeLinkNode findParent(TreeLinkNode pNode){
        if(pNode.next==null){
            // 程序执行到此处，说明没有父节点。那么当前节点就是根节点
            return pNode;
        }
        return findParent(pNode.next);
    }
}