【40】二叉树子结构

简介: 题目:输入两个二叉树A和B的根节点,判断二叉树B是否为A的子结构分析:1. 两个二叉树如下所示                      A树                                                                    B树    2. 要查找树A中是否包含数B一样的子结构,我们可以分成两步。


题目:输入两个二叉树A和B的根节点,判断二叉树B是否为A的子结构


分析:

1. 两个二叉树如下所示

                      A树                                                                    B树

    


2. 要查找树A中是否包含数B一样的子结构,我们可以分成两步。

   (1)第一步:先在树A中找到和树B的根节点的值一样的结点

   (2)第二步:判断从A中找到的和树B根节点的值一样的结点是否包含树B一样的结构


3. 例如上面的两颗子树中,树A中总共有两个值为8的结点,因为我们要判断两次是否B为A的子结构。



代码:

//二叉树结点
struct BinaryTreeNode{
    int value;
    BinaryTreeNode *lsonNode;
    BinaryTreeNode *rsonNode;
}; 

//第二步 :判断是否满足 
bool IsOk(BinaryTreeNode *root1, BinaryTreeNode *root2){
    //空树 
	if(root2 == NULL){
       return true;
	}
	if(root1 == NULL){
       return false;
	}
	//结点值不同肯定不是子树 
	if(root1->value != root2->value){
       return false;
	}
	else{
       return IsOk(root1->lsonNode, root2->lsonNode)
            &&IsOk(root1->rsonNode, root2->rsonNode);
	}
} 

//第一步:枚举树A判断B是不是子结构
bool IsSubTree(BinaryTreeNode *rootOne, BinaryTreeNode *rootTwo){
    //树为空的情况 
	if(rootTwo == NULL){
       return true;
    }
    if(rootOne == NULL){
       return false;
	}
	//根节点值一样 
    if(rootOne->value == rootTwo->value){
       //判断树A是否包含树B 
       if(IsOk(rootOne, rootTwo)){
          return true;
	   }
	}
    return IsSubTree(rootOne->lsonNode, rootTwo)
         ||IsSubTree(rootOne->rsonNode, rootTwo); 
} 


相关文章
|
存储 C++
二叉树搜索树的应用
二叉树搜索树的应用
76 1
【剑指offer】-树的子结构-17/67
【剑指offer】-树的子结构-17/67
|
10月前
|
算法 程序员 测试技术
【数据结构-二叉树 九】【树的子结构】:树的子结构
【数据结构-二叉树 九】【树的子结构】:树的子结构
97 0
|
10月前
|
算法 Java 程序员
【算法训练-二叉树 五】【最近公共祖先】二叉树的最近公共祖先、二叉搜索树的最近公共祖先
【算法训练-二叉树 五】【最近公共祖先】二叉树的最近公共祖先、二叉搜索树的最近公共祖先
78 0
|
10月前
|
算法
树的深度优先和广度优先
树的深度优先和广度优先
53 0
|
算法
修理牧场( 哈夫曼算法 ,贪心 )
修理牧场( 哈夫曼算法 ,贪心 )
221 0
剑指offer 25. 树的子结构
剑指offer 25. 树的子结构
73 0
剑指offer_二叉树---树的子结构
剑指offer_二叉树---树的子结构
84 0
|
算法 前端开发 程序员
树的子结构
树的子结构
树的子结构
《二叉树刷题计划》——相同的树、对称二叉树、另一棵树的子树
《二叉树刷题计划》——相同的树、对称二叉树、另一棵树的子树
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等