题目描述
请设计一个算法,寻找二叉树中指定结点的下一个结点(即中序遍历的后继)。
给定树的根结点指针TreeNode* root和结点的值int p,请返回值为p的结点的后继结点的值。保证结点的值大于等于零小于等于100000且没有重复值,若不存在后继返回-1。
思路:用中序遍历的下一个就是题目所说的下一个结点
代码如下:
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
*/
public class Successor {
}
ArrayList<TreeNode> list =new ArrayList<TreeNode>();
public int findSucc(TreeNode root, int p) {
// write code here
zhongxu(root);
for(int i=0;i<list.size()-1;i++){
//为什么用list.size()-1,是因为到i=list.size()-2的时候
//如果还不相等就只有两种情况
//(1)最后一个相等所以返回-1没有后继.(2).根本没有相等的值所以返回-1.
if(p==list.get(i).val){
return list.get(i+1).val;
}
}
return -1;
}
public void zhongxu(TreeNode root){//中序遍历
if(root!=null){
zhongxu(root.left);
list.add(root);
zhongxu(root.right);
}
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)