另一棵树的子树

题目

题目来源：力扣（LeetCode）

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

思路分析

要判断一个树 t 是不是树 s 的子树，那么可以判断 t 是否和树 s 的任意子树相等。个题的做法就是在 s 的每个子节点上，判断该子节点是否和 t 相等。

判断两个树是否相等的三个条件是与的关系，即：

1. 当前两个树的根节点值相等
2. 并且，s 的左子树和 t 的左子树相等
3. 并且，s 的右子树和 t 的右子树相等

而判断 t 是否为 s 的子树的三个条件是或的关系，即：

1. 当前两棵树相等
2. 或者，t 是 s 的左子树
3. 或者，t 是 s 的右子树

算法：

1. 定义isSameTree()用来判断两个树是否相同
2. 首先判断s和t是否相同，相同返回true
3. 不相同就递归判断s的左右子树是否和t相同

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} subRoot
 * @return {boolean}
 */
const isSubtree = (s, t) => {
  // 递归出口
  if (!s) return false;
  // 若两个树相同，肯定是true
  if (isSameTree(s, t)) return true;
  // 不相同，就递归判断s的左右子树
  return isSubtree(s.left, t) || isSubtree(s.right, t);
};
// 判断两个树是否相同
const isSameTree = (p, q) => {
  if (!p && !q) return true;
  if (p && q && p.val === q.val && isSameTree(q.left, p.left) &&
    isSameTree(q.right, p.right)) {
    return true;
  }
  return false;
};