剑指offer22 JZ8 二叉树的下一个结点

思路

• 总概：进行中序遍历 将所有的节点添加到arraylist里面，然后在进行一次遍历对比，找到后返回相同节点的下一个节点。
• 注意：我们首先要根据给定输入中的结点指针向父级进行迭代，直到找到该树的根节点；然后根据根节点进行中序遍历，当遍历到和给定树节点相同的节点时，下一个节点就是我们的目标返回节点
• 具体做法：

1. step 1：首先先根据当前给出的结点找到根节点
2. step 2：然后根节点调用中序遍历
3. step 3：将中序遍历结果存储下来
4. step 4：最终拿当前结点匹配是否有符合要求的下一个结点

/*
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 {
    ArrayList<TreeLinkNode> array=new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode root=pNode;
      //寻找根节点
        while(root.next != null) root = root.next;
        inoder(root);
      //查找
        for(int i=0;i<array.size();i++){
            TreeLinkNode cur=array.get(i);
            if(cur==pNode && i+1<array.size()){
                return array.get(i+1);
            }
        }
        return null;
    }
    public void inoder(TreeLinkNode node){
        if(node!=null){
            inoder(node.left);
          //添加
            array.add(node);
            inoder(node.right);
            
        }
    }
}