剑指Offer--树的子结构(JS)

mac2022-09-22  6

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

function HasSubtree(pRoot1, pRoot2) { // 两树任意一个为空或都为空,返回false if(pRoot2==null || pRoot1==null){ return false } //判断树2跟树1结构、树2跟树1左子树结构、树2跟树1右子树结构,有一个返回true,则树2是树1的子结构 return doesTree1HasTree2(pRoot1,pRoot2) || doesTree1HasTree2(pRoot1.left,pRoot2) || doesTree1HasTree2(pRoot1.right,pRoot2) } function doesTree1HasTree2(tree1, tree2){ //终止条件 if(tree2==null){ return true } if(tree1==null){ return false } if(tree1.val!==tree2.val){ return false } //递归判断双方每个节点是否一样,直至一方为空,终止跳出程序 return doesTree1HasTree2(tree1.left,tree2.left) && doesTree1HasTree2(tree1.right,tree2.right) }

 

最新回复(0)