Jianbo Dai's

mq044.另一个树的子树

 
  • Jan 06, 2021

题目链接

啊这个题如果用暴力做法的话就是枚举s中的节点然后和t的根结点比较，找到后再进行两棵树的遍历去判断是否相等。如1所示，这样做的时间复杂度为O( s x t )，空间复杂度为O(max{d_s, d_t})，d表示树的深度。
另外一种方法是在DFS序列上做串匹配。我们首先要了解一个小套路：一棵子树上的点在DFS序列（即先序遍历）中是连续的。了解了这个小套路之后，我们可以确定这个问题的方向就是：把s和t先转换成DFS序，然后看t的DFS序是否是s的DFS序的子串。这样做一定正确吗，其实不一定，假设s有两个节点，1是根，2是左孩子，而t也有两个节点，1也是根，但是2是右孩子。这样一来s和t的DFS序列相同可是t并不是s的子树。由此可见，“s的DFS序包含t的DFS序”是“t是s子树”的必要不充分条件，所以单纯这样做是不正确的。为了解决这个问题，我们引入两个空值lNull和rNull，当一个节点的左孩子或者右孩子为空时，就插入这两个空值，这样DFS序列就唯一对应一棵树。然后，在判断“s的DFS序包含t的DFS序”的时候，可以暴力匹配也可以使用KMP算法。该方法如2所示，其中搜索时用了KMP算法。这个算法的时间复杂度是O( s + t )，空间复杂度是O( s + t )。

python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSubtree1(self, s: TreeNode, t: TreeNode) -> bool:
        if not s:
            return False
        if self.helper(s, t):
            return True
        else:
            return self.isSubtree1(s.left, t) or self.isSubtree1(s.right, t)

    def helper(self, tmps, tmpt):
        if not tmps and not tmpt:
            return True
        if not tmps or not tmpt:
            return False
        return tmps.val == tmpt.val and self.helper(tmps.left, tmpt.left) and self.helper(tmps.right, tmpt.right)

    def isSubtree2(self, s: TreeNode, t: TreeNode) -> bool:
        def _serialize(root):
            if not root:
                return '#'
            # Split symbol ',': Solve the problem of case [12], [2]
            return ',' + str(root.val) + ',' + _serialize(root.left) + ',' + _serialize(root.right)
        sstr = _serialize(s)
        tstr = _serialize(t)
        print(sstr, tstr)
        return sstr.find(tstr) != -1

C++:

class Solution1 {
public:
    bool check(TreeNode *o, TreeNode *t) {
        if (!o && !t) {
            return true;
        }
        if ((o && !t) || (!o && t) || (o->val != t->val)) {
            return false;
        }
        return check(o->left, t->left) && check(o->right, t->right);
    }

    bool dfs(TreeNode *o, TreeNode *t) {
        if (!o) {
            return false;
        }
        return check(o, t) || dfs(o->left, t) || dfs(o->right, t);
    }

    bool isSubtree(TreeNode *s, TreeNode *t) {
        return dfs(s, t);
    }
};

class Solution2 {
public:
    vector <int> sOrder, tOrder;
    int maxElement, lNull, rNull;

    void getMaxElement(TreeNode *o) {
        if (!o) {
            return;
        }
        maxElement = max(maxElement, o->val);
        getMaxElement(o->left);
        getMaxElement(o->right);
    }

    void getDfsOrder(TreeNode *o, vector <int> &tar) {
        if (!o) {
            return;
        }
        tar.push_back(o->val);
        if (o->left) {
            getDfsOrder(o->left, tar);
        } else {
            tar.push_back(lNull);
        }
        if (o->right) {
            getDfsOrder(o->right, tar);
        } else {
            tar.push_back(rNull);
        }
    }

    bool kmp() {
        int sLen = sOrder.size(), tLen = tOrder.size();
        vector <int> fail(tOrder.size(), -1);
        for (int i = 1, j = -1; i < tLen; ++i) {
            while (j != -1 && tOrder[i] != tOrder[j + 1]) {
                j = fail[j];
            }
            if (tOrder[i] == tOrder[j + 1]) {
                ++j;
            }
            fail[i] = j;
        }
        for (int i = 0, j = -1; i < sLen; ++i) {
            while (j != -1 && sOrder[i] != tOrder[j + 1]) {
                j = fail[j];
            }
            if (sOrder[i] == tOrder[j + 1]) {
                ++j;
            }
            if (j == tLen - 1) {
                return true;
            }
        }
        return false;
    }

    bool isSubtree(TreeNode* s, TreeNode* t) {
        maxElement = INT_MIN;
        getMaxElement(s);
        getMaxElement(t);
        lNull = maxElement + 1;
        rNull = maxElement + 2;

        getDfsOrder(s, sOrder);
        getDfsOrder(t, tOrder);

        return kmp();
    }
};
Search