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

题目描述

输入两棵二叉树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) }