572.另一个树的子树

发表于 | 分类于
字数统计: 316 | 阅读时长 ≈ 1

一、题目描述

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

1
2
3
4
5
    3
   / \
  4   5
 / \
1   2

给定的树 t：

1
2
3
  4 
 / \
1   2

返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s：

1
2
3
4
5
6
7
    3
   / \
  4   5
 / \
1   2
   /
  0

给定的树 t：

1
2
3
  4
 / \
1   2

返回 false。

二、题解

1.递归

1.1 思路

  1. 什么叫子树？

    答：树B是树A的子集。即A与B相等；或B是A的左子树或右子树的子树。

1.2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSame(struct TreeNode *s, struct TreeNode *t)
{
    if (s == NULL && t == NULL)
        return true;
    return (s && t) && s->val == t->val && isSame(s->left, t->left) && isSame(s->right, t->right);
}

bool isSubtree(struct TreeNode *s, struct TreeNode *t)
{
    if (s == NULL && t == NULL)
        return true;
    if (s == NULL && t != NULL)
        return false;
    return isSame(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
}