输入两棵二叉树A,B,判断B是不是A的子结构。(我们约定空树不是任意一个树的子结构)
假如给定A为{8,8,7,9,2,#,#,#,#,4,7},B为{8,9,2},2个树的结构如下,可以看出B是A的子结构
数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000
{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}
true
{1,2,3,4,5},{2,4}
true
{1,2,3},{3,1}
false
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function HasSubtree(pRoot1, pRoot2) { if(!pRoot1 || !pRoot2) return false; let result = false if(pRoot1.val === pRoot2.val){ result = isSameSubtree(pRoot1, pRoot2) } if(!result && pRoot1.left){ result = HasSubtree(pRoot1.left, pRoot2) } if(!result && pRoot1.right){ result = HasSubtree(pRoot1.right, pRoot2) } return result } function isSameSubtree(pRoot1, pRoot2){ if(!pRoot1 && pRoot2) return false; if(!pRoot2) return true const { left:left1, right:right1,val:val1 } = pRoot1; const { left:left2, right:right2, val:val2 } = pRoot2; let result = false; if(val1 === val2){ result = isSameSubtree(left1, left2) && isSameSubtree(right1, right2) } return result } module.exports = { HasSubtree : HasSubtree };
function HasSubtree(A, B) { // write code here if(!A||!B){ return false } return isSameTree(A, B) || HasSubtree(A.left, B) || HasSubtree(A.right, B) }; var isSameTree = function(A, B){ if(!B) return true if(!A) return false if(A.val !== B.val) return false return isSameTree(A.left, B.left) && isSameTree(A.right, B.right) }
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ //注意子结构,和子树并不一致,子树的判断:我的想法是先通过b的中序遍历得到数组, //再去判断a的根节点是不是在b的数组中,再去判断左右节点是不是也一样,子树的意思是包含了 //一个结点,就得包含这个结点下的所有节点,一棵大小为n的二叉树有n个子树,就是分别以每个结点 //为根的子树。子结构的意思是包含了一个结点,可以只取左子树或者右子树,或者都不取。 //子树的判断要比子结构复杂 function HasSubtree(pRoot1, pRoot2) { if(!pRoot1 || !pRoot2) return false return isSubTree(pRoot1,pRoot2)||HasSubtree(pRoot1.left,pRoot2)||HasSubtree(pRoot1.right,pRoot2) function isSubTree(p,q){ if(!q) return true if(!p) return false if(p.val===q.val){ return isSubTree(p.left,p.left)&&isSubTree(p.right,p.right) } else return false } }// write code here
function HasSubtree(pRoot1, pRoot2) { // write code here if(pRoot2 == null || pRoot1 == null) return false; if(pRoot1.val == pRoot2.val){ if(IsEqual(pRoot1, pRoot2) == true) return true; } return HasSubtree(pRoot1.left, pRoot2)||HasSubtree(pRoot1.right, pRoot2); } function IsEqual(pRoot1, pRoot2){ if(pRoot2 == null) return true; if(pRoot1 == null && pRoot2 !=null) return false; if(pRoot1.val != pRoot2.val) return false; else if(pRoot1.val == pRoot2.val) return IsEqual(pRoot1.left, pRoot2.left)&&IsEqual(pRoot1.right, pRoot2.right); }
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ /** * 我的解题思路: * 1.思路是比较简单的,从父树的根节点开始,依次与子树进行节点比较 * 2.当找到相同节点时,同时递归比较左节点和右节点是否相同 * 4.这里有几个需要注意的点: * - 递归比较时的终止条件为父树节点不存在或者子树节点不存在,且两种情况返回值不同 * - 递归终止时,需要先判断子树节点,再判断父树节点 * - 对父树根节点比较时,需要用额外空间存储每次比较的结果,用于判断下次是否需要进行比较 * * @param {*} pRoot1 * @param {*} pRoot2 */ function HasSubtree(pRoot1, pRoot2) { // write code here if (!pRoot1 || !pRoot2) { return false; } const func = (p1, p2) => { if (!p2) { return true; } if (!p1) { return false; } if (p1.val === p2.val) { return func(p1.left, p2.left) && func(p1.right,p2.right); } return false; }; let result = false; if (pRoot1.val === pRoot2.val) { result = func(pRoot1, pRoot2); } if (!result) { result = func(pRoot1.left, pRoot2); } if (!result) { result = func(pRoot1.right, pRoot2); } return result; } /** * 评论区TOP的解题思路: * 思路跟我的思路一致,不过有一些优化的写法 * * @param {*} pRoot1 * @param {*} pRoot2 */ function topHasSubtree(pRoot1, pRoot2) { // write code here if (!pRoot1 || !pRoot2) { return false; } const func = (p1, p2) => { if (!p2) { return true; } if (!p1) { return false; } return p1.val === p2.val ? func(p1.left, p2.left) && func(p1.right,p2.right) : false; }; return func(pRoot1, pRoot2) || func(pRoot1.left, pRoot2) || func(pRoot1.right, pRoot2); }
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function HasSubtree(pRoot1, pRoot2) { // write code here if(!pRoot1 || !pRoot2) return false; if(compare(pRoot1, pRoot2)){ return true; }else{ let status = false; if(pRoot1.left){ status = status || HasSubtree(pRoot1.left, pRoot2); } if(pRoot1.right){ status = status || HasSubtree(pRoot1.right, pRoot2); } return status; } } function compare(root1, root2){ if(!root2) return true; if(!root1 || root1.val !== root2.val){ return false; }else{ return compare(root1.left, root2.left) && compare(root1.right, root2.right) } }
function HasSubtree(pRoot1, pRoot2) { let result = false; if (pRoot1 && pRoot2) { if (pRoot1.val === pRoot2.val) { result = compare(pRoot1, pRoot2); } if (!result) { result = HasSubtree(pRoot1.right, pRoot2); } if (!result) { result = HasSubtree(pRoot1.left, pRoot2); } } return result; } function compare(pRoot1, pRoot2) { if (pRoot2 === null) { return true; } if (pRoot1 === null) { return false; } if (pRoot1.val !== pRoot2.val) { return false; } return compare(pRoot1.right, pRoot2.right) && compare(pRoot1.left, pRoot2.left); }
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
/*先序遍历*/
function preOrder(tmp,arr){
arr.push(tmp.val);
if(tmp.left != null)
preOrder(tmp.left,arr);
if(tmp.right != null)
preOrder(tmp.right,arr);
}
function HasSubtree(pRoot1, pRoot2)
{
// write code here
if(pRoot2 == null)
return false;
if(pRoot1 == null && pRoot2 != null)
return false;
var arrc = [],
arrf = [];
preOrder(pRoot1,arrf);
preOrder(pRoot2,arrc);
if(arrf.join().includes(arrc.join()))
return true
else
return false;
}
function sameTree(pRoot1, pRoot2){ if(pRoot2 === null){ return true; } if(pRoot1 === null && pRoot2 !== null){ return false; } return pRoot1.val === pRoot2.val && sameTree(pRoot1.left, pRoot2.left) && sameTree(pRoot1.right, pRoot2.right); } function HasSubtree(pRoot1, pRoot2) { if(pRoot1 === null || pRoot2 === null){ return false; } if(sameTree(pRoot1, pRoot2)){ return true; } return HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2); }
function isSubtree(pRoot1, pRoot2) { if (!pRoot2) return true; if (!pRoot1) return false; if (pRoot1.val != pRoot2.val) { return false; } else { return isSubtree(pRoot1.left, pRoot2.left) && isSubtree(pRoot1.right, pRoot2.right); } } function HasSubtree(pRoot1, pRoot2) { // write code here if (pRoot2 == null || pRoot1 == null) return false; return isSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2); }
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function HasSubtree(pRoot1, pRoot2) { // write code here if(pRoot1 == null || pRoot2 == null){ return false; } if(pRoot1.val == pRoot2.val && pRoot2.right == null && pRoot2.left == null){ return true; } if(pRoot1.val == pRoot2.val){ if(!pRoot1.left && !pRoot2.left){ return HasSubtree(pRoot1.right, pRoot2.right); } if(!pRoot1.right && !pRoot2.right){ return HasSubtree(pRoot1.left, pRoot2.left); } if(HasSubtree(pRoot1.left, pRoot2.left) && HasSubtree(pRoot1.right, pRoot2.right)){ return true; } } return (HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2)) }
//Javascript 描述,用flag表示函数状态。 function HasSubtree(p1, p2,flag) { var f=HasSubtree; if(flag && !p2) return true; if(!p1 || !p2) return false; if(p1 && p2 && p1.val == p2.val) return f(p1.left,p2.left,true) && f(p1.right,p2.right,true) || f(p1.left,p2)||f(p1.right,p2); return f(p1.left,p2) || f(p1.right,p2); }