剑指offer26 树的子结构

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

链接: https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/

题意

输入两棵二叉树A和B，判断B是不是A的子结构

解法

递归
设计一个函数专门判断是否包含子树
注意判断每次子节点是否为空
精简到两个函数实现

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isHave(TreeNode* A, TreeNode* B) {
        if (!A) return false;
        if (A -> val != B -> val) return false;
        if (B -> left && B -> right) return isHave(A -> left, B -> left) && isHave(A -> right, B -> right);
        if (B -> left) return isHave(A -> left, B -> left);
        if (B -> right) return isHave(A -> right, B -> right);
        return true;
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (!A || !B) return false;
        if (A -> val == B -> val) {
            if (isHave(A, B)) {
                return true;
            }
        }
        return isSubStructure(A -> left, B) || isSubStructure(A -> right, B);
    }
};