剑指 Offer 26 树的子结构

概述

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

序列化后将问题转换为字符串中是否存在给定子串

这个思路是不行的，因为 B 可能并不是 A 中的一个完整子树！

递归法

首先找出 A 中所有与 B 的根节点相同的节点，然后遍历 B，同时遍历 A 检查其是否支持同样方式的遍历。

class Solution {
public:
    vector<TreeNode*> nodes;
    int target;
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (!B) return false;
        target = B->val;
        travel(A);
        for (auto& node : nodes) {
            if (verify(node, B)) return true;
        }
        return false;
    }

    bool verify(TreeNode* A, TreeNode* B) {
        if (!B) return true;
        if (!A) return false;
        if (A->val != B->val) return false;
        return verify(A->left, B->left) && verify(A->right, B->right);
    }

    void travel(TreeNode* root) {
        if (!root) return;
        if (root->val == target) nodes.push_back(root);
        travel(root->left);
        travel(root->right);
    }
};

其实没必要存下来，一旦找到一个可能的节点立刻开始验证就好：

class Solution {
public:
    int target;
    TreeNode* B;
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (!B) return false;
        this->B = B;
        target = B->val;
        return travel(A);
    }

    bool verify(TreeNode* A, TreeNode* B) {
        if (!B) return true;
        if (!A) return false;
        if (A->val != B->val) return false;
        return verify(A->left, B->left) && verify(A->right, B->right);
    }

    bool travel(TreeNode* root) {
        if (!root) return false;
        if (root->val == target) {
            if (verify(root, B)) return true;
        };
        return travel(root->left) || travel(root->right);
    }
};

Links: sword-offer-26

未经允许，禁止转载，本文源站链接：https://iamazing.cn/