树的子结构

Posted on | In | | reads times

树的子结构

题目描述

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

重复两步，采用递归

  1. 根节点是否相同
  2. 相同检查剩余节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    let res=false;
    if(pRoot1===null)return false;
    if(pRoot2===null)return false;
    if(pRoot1.val==pRoot2.val) res=tree1hastree2(pRoot1,pRoot2)
    if(!res)res=HasSubtree(pRoot1.left,pRoot2)
    if(!res)res=HasSubtree(pRoot1.right,pRoot2)
    return res;
}
function tree1hastree2(pRoot1,pRoot2)
{
    if(pRoot2===null)return true;
    if(pRoot1===null)return false;
    if(pRoot1.val!==pRoot2.val)return false;
    return tree1hastree2(pRoot1.left,pRoot2.left)&&tree1hastree2(pRoot1.right,pRoot2.right);
}