題目描述

樹的子結(jié)構(gòu)

輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）

思路

使用遞歸，逐一比較左右子節(jié)點(diǎn)

Code

• JavaScript

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function HasSubtree(a, b)
{
    // write code here
  if (a == null || b == null) return false;
  return isSubtree(a, b) || HasSubtree(a.left, b) || HasSubtree(a.right, b);
}
function isSubtree(a, b)
{
  if (b == null) return true;
  if (a == null) return false;
  if (a.val === b.val) {
    return isSubtree(a.left, b.left) && isSubtree(a.right, b.right)
  } 
  return false;
}