输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
public static boolean check(TreeNode h, TreeNode t2) {
if (t2 == null) {
return true;
}
if (h == null || h.val != t2.val) {
return false;
}
return check(h.left, t2.left) && check(h.right, t2.right);
}
public static boolean HasSubtree(TreeNode t1, TreeNode t2) {
if (t2 == null) {
return false;
}
if (t1 == null) {
return false;
}
return check(t1, t2) || HasSubtree(t1.left, t2) || HasSubtree(t1.right, t2);
}
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
public static boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length < 1) return false;
return helper(sequence, 0, sequence.length - 1);
}
public static boolean helper(int [] arr, int left, int right){
if (left == right) return true;
int root = arr[right];
int i;
for(i = left; i < right; i++){
if (arr[i] > root){
break;
}
}
int j = i;
for(; j < right; j++){
if (arr[j] < root){
return false;
}
}
boolean l = true;
if (i > left){
l = helper(arr, left,i - 1);
}
boolean r = true;
if (i < right){
r = helper(arr, i, j -1);
}
return l && r;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。