LEETCODE ALGORITHM:572. Subtree of Another Tree

发表于 更新于 分类于 Waline： 阅读次数：

题目

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1: Given tree s:

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

Given tree t:

1
2
3
  4 
 / \
1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2: Given tree s:

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

Given tree t:

1
2
3
  4
 / \
1   2

Return false.

题解

  1. 在树s找到与树t根节点根节点相同的节点，由于存在重复节点值，放入数组保存
  2. 从所有保存的相同节点出发检查下面的节点是否相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//两次dfs，时间负责度高
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<TreeNode*> same;
    void dfs(TreeNode* root,TreeNode* t)
    {
        if(root->val==t->val)
        {
            same.push_back(root);
        }
        if(root->left) dfs(root->left,t);
        if(root->right) dfs(root->right,t);
    }
    bool cmp(TreeNode* s,TreeNode* t)
    {
        if(s==nullptr&&t==nullptr) return true;
        else if(s==nullptr||t==nullptr) return false;
        if(s->val!=t->val) return false;
        else{
            return cmp(s->left,t->left)&&cmp(s->right,t->right);
        }
    }
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        dfs(s,t);
        bool ans=0;
        for(int i=0;i<same.size();i++)
        {
            ans|=cmp(same[i],t);
        }
        return ans;
    }
};

中序遍历，查找是否存在公共序列

不用search，自己写kmp会快不少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//反而更慢了？？
class Solution {
private:
    vector<int> ss,tt;
    int lNull,rNull;
    void dfs(TreeNode* root,vector<int>& tmp)
    {
        tmp.push_back(root->val);
        if(root->left) dfs(root->left,tmp);
        else tmp.push_back(lNull);
        if(root->right) dfs(root->right,tmp);
        else tmp.push_back(rNull);
    }
public:
    bool isSubtree(TreeNode *s, TreeNode *t) {
        lNull=INT_MIN;rNull=INT_MAX;
        dfs(s,ss);
        dfs(t,tt);
        if(search(ss.begin(),ss.end(),tt.begin(),tt.end())!=ss.end()) return true;
        else return false;
    }
};