提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
题目描述
输入描述: 输入分为2段,第一段是整体的二叉树,第二段是给定二叉树节点的值,后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNext里面,用户得到的输入只有一个子树根节点 返回值描述: 返回传入的子树根节点的下一个节点,后台会打印输出这个节点 示例1 输入: {8,6,10,5,7,9,11},8 返回值: 9
示例2 输入: {8,6,10,5,7,9,11},6
返回值: 7 示例3 输入: {1,2,#,#,3,#,4},4 返回值: 1 示例4 输入: {5},5 返回值: “null” 说明: 不存在,后台打印"null"
解题过程
解题思路
1、先将根节点找出来,方法是链表的遍历; 2、根据这个根节点将中序遍历结果放进列表; 3、遍历列表找到对应的pNode,如果pNode的下一个存在就直接返回下一个; 4、结尾还没返回,就返回null表示没有这个节点。
import java.util.*;
public class Solution {
TreeLinkNode nextP = null;
List<TreeLinkNode> list = new ArrayList<>();
public TreeLinkNode GetNext(TreeLinkNode pNode) {
TreeLinkNode root = pNode;
while(root.next != null){
root = root.next;
}
GetNextFunction(root);
for(int i = 0; i < list.size(); i++){
if(list.get(i) == pNode){
if(i + 1 < list.size()){
return list.get(i + 1);
}
}
}
return null;
}
public void GetNextFunction(TreeLinkNode root){
if(root == null){
return;
}
GetNextFunction(root.left);
list.add(root);
GetNextFunction(root.right);
}
}
总结
|