572.另一棵树的子树

链接：572.另一棵树的子树
难度：Easy
标签：树、深度优先搜索、二叉树、字符串匹配、哈希函数
简介：给定两个非空二叉树 s 和 t，检验  s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

题解 1 - javascript

• 编辑时间：2020-05-07
• 执行用时：84ms
• 内存消耗：41.5MB
• 编程语言：javascript
• 解法介绍：先遍历获取所有值相等的节点，通过中序遍历判断是否每项值都相等

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} s
 * @param {TreeNode} t
 * @return {boolean}
 */
var isSubtree = function (s, t) {
  function searchNode(val) {
    const queue = inorder(s);
    const resArr = [];
    for (const node of queue) {
      if (node.val === val) resArr.push(node);
    }
    return resArr;
  }
  function inorder(node) {
    const queue = [];
    function _inorder(node) {
      if (node.left !== null) _inorder(node.left);
      queue.push(node);
      if (node.right !== null) _inorder(node.right);
    }
    _inorder(node);
    return queue;
  }
  function sameArrVal(arr1, arr2) {
    const len1 = arr1.length;
    if (len1 !== arr2.length) return false;
    for (let i = 0; i < len1; i++) if (arr1[i].val !== arr2[i].val) return false;
    return true;
  }
  const sameNodeArr = searchNode(t.val);
  if (sameNodeArr.length === 0) return false;
  const tArr = inorder(t);
  for (const node of sameNodeArr) {
    if (sameArrVal(inorder(node), tArr)) return true;
  }
  return false;
};

题解 2 - python

• 编辑时间：2024-08-04
• 执行用时：58ms
• 内存消耗：16.51MB
• 编程语言：python
• 解法介绍：序列化。

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def stringify(node: Optional[TreeNode]) -> str:
            if not node: return ''
            return f'[{node.val}, {stringify(node.left)}, {stringify(node.right)}]'
        return stringify(subRoot) in stringify(root)