100.相同的树

链接：100.相同的树
难度：Easy
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：给定两个二叉树，编写一个函数来检验它们是否相同。

题解 1 - typescript

• 编辑时间：2020-08-07
• 执行用时：88ms
• 内存消耗：38.1MB
• 编程语言：typescript
• 解法介绍：序列化后比较字符串即可。

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  return serialize(p) === serialize(q);
  function serialize(node: TreeNode | null): string {
    const queue = [node];
    const hasNum = () => queue.some(v => v !== null);
    let str = '';
    while (hasNum()) {
      const node = queue.shift() as TreeNode | null;
      if (node === null) {
        str += 'null,';
        continue;
      } else {
        str += node.val + ',';
      }
      if (node.left !== null) queue.push(node.left);
      else queue.push(null);
      if (node.right !== null) queue.push(node.right);
      else queue.push(null);
    }
    return `[${str.substr(0, str.length - 1)}]`;
  }
}

题解 2 - c

• 编辑时间：2021-11-27
• 内存消耗：5.7MB
• 编程语言：c
• 解法介绍：递归。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    // 同为NULL则相同
    if (p == NULL && q == NULL) return 1;
    // 若其中一个为NULL或者值不一样就不同,
    if (p == NULL || q == NULL || p->val != q->val) return 0;
    // 否则递归子树
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}