leetcode 572. Subtree of Another Tree 子树判断 + 深度优先遍历DFS

客官°小女子只卖身不卖艺 2022-06-03 04:23 120阅读 0赞

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:

3
    / \
    4   5
    / \
    1   2

Given tree t:  
4  
/ \\  
1 2  
Return true, because t has the same structure and node values with a subtree of s.  
Example 2:  
Given tree s:

3
    / \
    4   5
    / \
    1   2
    /
    0

Given tree t:  
4  
/ \\  
1 2  
Return false.

本题题意很简单，直接递归遍历即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    
    /*
    struct TreeNode
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        bool isSubtree(TreeNode* s, TreeNode* t) 
        {
            if (s == NULL)
                return false;
            else if (isSame(s, t) == true)
                return true;
            else
                return isSubtree(s->left, t) || isSubtree(s->right, t);
        }
    
        bool isSame(TreeNode* s, TreeNode* t)
        {
            if (s == NULL && t == NULL)
                return true;
            else if (s == NULL && t != NULL || s != NULL && t == NULL)
                return false;
            else
            {
                if (s->val != t->val)
                    return false;
                else
                    return isSame(s->left,t->left) && isSame(s->right,t->right);
            }
        }
    };