思路
- 总概:进行中序遍历 将所有的节点添加到arraylist里面,然后在进行一次遍历对比,找到后返回相同节点的下一个节点。
- 注意:我们首先要根据给定输入中的结点指针向父级进行迭代,直到找到该树的根节点;然后根据根节点进行中序遍历,当遍历到和给定树节点相同的节点时,下一个节点就是我们的目标返回节点
- 具体做法:
- step 1:首先先根据当前给出的结点找到根节点
- step 2:然后根节点调用中序遍历
- step 3:将中序遍历结果存储下来
- 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);
}
}
}