[数据结构与算法]JZ8 二叉树的下一个结点

描述

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

?思路

1.根据给定的节点pNode找到二叉树的起始节点。

2.中序遍历起始节点，将遍历的结果存在ArrayList中。

3.将得到的ArrayList中取出pNode的下标，返回ArrayList中下标+1位置的节点即可。

代码

/*
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 {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        TreeLinkNode temp = pNode;
        ArrayList<TreeLinkNode> list = new ArrayList<>();
        while(temp.next != null){
            temp = temp.next;
        }
        midshow(temp,list);
        int index = list.indexOf(pNode);
        if(index+1>=list.size()){
            return null;
        }
        return list.get(index+1);
    }
    public void midshow(TreeLinkNode pNode,ArrayList list){
        if(pNode.left != null){
            midshow(pNode.left,list);
        }
        list.add(pNode);
        if(pNode.right != null){
            midshow(pNode.right,list);
        }
        
        
    }
}