C语言重构【572】另一个树的子树

青旅半醒 2022-11-21 11:52 151阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
    
    示例 1:
    给定的树 s:
    
         3
        / \
       4   5
      / \
     1   2
    给定的树 t：
    
       4 
      / \
     1   2
    返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
    
    示例 2:
    给定的树 s：
    
         3
        / \
       4   5
      / \
     1   2
        /
       0
    给定的树 t：
    
       4
      / \
     1   2
    返回 false。

#### 方案： ####

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    class Solution
    { 
    public:
        bool isSubtree(TreeNode *s, TreeNode *t)
        { 
            if (s == NULL)
                return false;
            if (s->val == t->val && isSameTree(s, t))
                return true;
            if (s->left != NULL && isSubtree(s->left, t))
                return true;
            if (s->right != NULL && isSubtree(s->right, t))
                return true;
            return false;
        }
    
        bool isSameTree(TreeNode *s, TreeNode *t)
        { 
            if ((s == NULL && t != NULL) || (s != NULL && t == NULL))
                return false;
            else if (s == NULL && t == NULL)
                return true;
            if (s->val == t->val)
            { 
                return isSameTree(s->left, t->left) && isSameTree(s->right, t->right);
            }
            else if (s->val != t->val)
                return false;
            return false;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(mn),其中mn分别为t和s的节点个数
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode