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

本文主要是介绍【leetcode】另一棵树的子树 c++，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

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

示例1:

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

示例2：

输入：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++的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！