【leetcode】另一棵树的子树 c++

题目描述:
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例1:
【leetcode】另一棵树的子树 c++

输入:root = [3,4,5,1,2], subRoot = [4,1,2]
输出:true

示例2:
【leetcode】另一棵树的子树 c++

输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出:false

提示:

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

代码:

/**
 * 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 issame(TreeNode* root1,TreeNode* root2){
        if(root1==nullptr&&root2==nullptr)return true;
        if(root1==nullptr||root2==nullptr)return false;
        if(root1->val!=root2->val)return false;
        return issame(root1->left,root2->left)&&issame(root1->right,root2->right);//!!!左子树和右子树都要分别相等
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root==nullptr&&subRoot==nullptr)return true;
        if(root==nullptr||subRoot==nullptr)return false;
        int issame_flag = false;
        if(root->val==subRoot->val){
            issame_flag=issame(root,subRoot);
        }
        return issame_flag||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot); //若当前节点为根的树不满足条件,则继续向下查找,判断左子树和右子树是否满足条件
    }
};

此题分为两步,第一步先判断两个二叉树是否相等第二步在一个二叉树中找与另一个二叉树相等的子树

1.判断二叉树相等:递归

递归终止条件:
①两个节点都为空,即两树所有节点都判断完了,return true
②两个节点只有一个为空,说明两个树结构不同,一个已经为空一个不为空,return false
③两个节点都不为空,但值不相同,两树一定不相等,return false

递归范围缩小式:
判断当前两树的根节点,若根节点相同后,再分别判断两树的左子树和右子树是否对应相同。

2.找与另一个二叉树相等的子树:递归

递归终止条件:
①两个树根节点都为空,return true
②两个树的根节点只有一个为空,说明两个树结构不同,return false
③两个树的根节点都不为空,但值不相同,两树一定不相等,return false(需要继续向下查看左子树和右子树是否满足要求)

递归范围缩小式:
判断以当前节点为根节点的树or以当前节点左子节点为根节点的树or以当前节点右子节点为根节点的树,是否与另一个二叉树相同。
【leetcode】另一棵树的子树 c++

上一篇:36. 二叉搜索树与双向链表


下一篇:合并两个有序链表——记录(C++)