LeetCode572 另一棵树的子树

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

链接: https://leetcode-cn.com/problems/merge-two-binary-trees

题意

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树

解法

和子树是对称树的题目相似，强化一下这种思路
dfs遍历节点 判断是否两棵树相同

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isSame(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr && t2 == nullptr) return true;
        if (t1 == nullptr || t2 == nullptr) return false;
        if (t1 -> val != t2 -> val) return false;
        return isSame(t1 -> left, t2 -> left) && isSame(t1 -> right, t2 -> right);

    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root) return false;
        if (isSame(root, subRoot)) return true;
        return isSubtree(root -> left, subRoot) || isSubtree(root -> right, subRoot);
    }
};