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

import java.util.ArrayList;

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

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
   //用这个顺序表存储中序遍历
    ArrayList<TreeLinkNode> arrNode = new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //给出二叉树层序遍历,给出一个节点值,求中序遍历中,结点的下一个节点值
        //先找到根节点,根据根节点进行中序遍历
        //再用目的端点去进行匹配
        //层序遍历的第一个节点为根节点
        //根节点的特点是next值为null
        TreeLinkNode root = pNode;
        while(root.next != null){
            root = root.next;
        }
        Inorder(root);
        //得到中序遍历,开始查找对应的节点,也就是当节点值的pNode时,返回它的下一个(如果有下一个的话)
        int n = arrNode.size();
        for(int i = 0; i < n; i++){
            if(pNode.val == arrNode.get(i).val){
                if(i < n-1){
                    return arrNode.get(i+1);
                }
            }
        }

        return null;
    }

    public void Inorder(TreeLinkNode root){
        //左根右
        if(root != null){
            Inorder(root.left); 
            arrNode.add(root);
            Inorder(root.right);
        }
    }
}