【剑指offer】17 树的子结构

题目描述

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

题目示例

输入：

{8,8,#,9,#,2,#,5},{8,9,#,2}

返回值：

true

解法分析

首先找A中与B根节点相同的节点r，然后比较A中以r为根节点的子树是否包含B的结构。

代码

 1 function HasSubtree(pRoot1, pRoot2)
 2 {
 3     // write code here
 4     //按题干要求，当root1或root2为null的时候，直接返回false
 5     if(pRoot1 === null || pRoot2 === null){
 6         return false;
 7     }else{
 8         var res = false;
 9         //当A的此节点与B的根节点相同时，调用Does1has2()对比A中以r为根节点的子树是否包含B的结构
10         if(pRoot1.val == pRoot2.val) res = Does1has2(pRoot1, pRoot2);
11         //若此节点与B的根节点不相同，则用A的左儿子节点与B根节点进行对比
12         if(!res) res = HasSubtree(pRoot1.left, pRoot2);
13         //若此节点和A的左儿子都与B的根节点不相同，则用A的右儿子节点与B根节点进行对比
14         if(!res) res = HasSubtree(pRoot1.right, pRoot2);
15     }
16     return res;
17 }
18 function Does1has2(node1, node2){
19     //B遍历完都能一一对应，表明B是A的子结构，返回true
20     if(node2 === null) return true;
21     //B没遍历完A却遍历完了，表明B不是A的子结构，返回false
22     if(node1 === null) return false;
23     //如果有节点对应不上，返回false
24     if(node1.val !== node2.val) return false;
25     //此节点对应上了，递归调用Does1has2()来对比子节点
26     return Does1has2(node1.left, node2.left) && Does1has2(node1.right, node2.right);
27 }

执行结果