二叉树4个题目
//二叉搜索树的公共祖先
public static TreeNodetask40(TreeNode root, TreeNode node1, TreeNode node2){
if (root ==null){
return root;
}
if(node1.valueroot.value){
return root;
}
if (node1.value < root.value && node2.value
return task40(root.leftchild,node1,node2);
}
if(node1.value>root.value && node2.value >root.value){
return task40(root.rightchild,node1,node2);
}
return null;
}
//二叉树的公共祖先
public static TreeNodetask41(TreeNode root, TreeNode node1, TreeNode node2){
if(root ==null|| node1 == root || node2 == root){
return root;
}
TreeNode left =task41(root.leftchild,node1,node2);
TreeNode right =task41(root.rightchild,node1,node2);
if(left !=null && right !=null){
return root;
}
return left !=null?left:right;
}
public static ArrayListrest =new ArrayList();
public static Listtask42(TreeNode root, int target){
back(root,target,new ArrayList());
return rest;
}
public static void back(TreeNode root, int target, ArrayList path){
target = target -root.value;
path.add(root.value);
if(target ==0 && root.leftchild ==null && root.rightchild ==null){
rest.add(new ArrayList<>(path));
}
if(root.leftchild !=null){
back(root.leftchild,target,path);
path.remove(path.size() -1);
}
if(root.rightchild !=null){
back(root.rightchild,target,path);
path.remove(path.size() -1);
}
}
//二叉树中的列表
public static boolean task43(TreeNode root, LinkedLIST head){
if (head ==null){
return true;
}
if(root ==null){
return false;
}
return task(root,head) ||task43(root.leftchild,head) ||task43(root.rightchild,head);
}
public static boolean task(TreeNode root, LinkedLIST head){
if (head ==null){
return true;
}
if(root ==null){
return false;
}
if(root.value != head.value){
return false;
}else{
return task(root.leftchild,head.next)||task(root.rightchild,head.next);
}
}
