判断树为另一树的子结构

缺乏、安全感 2022-08-08 00:58 153阅读 0赞

输入两棵二叉树 A 和 B，判断树 B 是不是 A 的子结构。  
例如，下图中的两棵树 A 和 B， 由于 A 中有一部分子树的结构和 B 是一样的，因此 B 就是 A  
的子结构。

思路：首先采用一种方式来遍历A树，发现A树的某个节点和B树的根节点的值相等，从这个节点开始遍历是否为A树的一部分。

bool IsSame(BinTree* first,BinTree* second)
    {
    	if(first == NULL && second == NULL)
    		return true;
    	if((first==NULL&&second!=NULL)|| (first!=NULL&&second==NULL))
    		return false;
    	if(first->value != second->value)
    		return false;
    	return (IsSame(first->left,second->left))&&(IsSame(first->right,second->right));
    }
    bool VerifyOfPart(BinTree* root,BinTree* part)
    {
    	stack<BinTree*> st;
    	if(part == NULL)
    		return true;
    	while(root != NULL || !st.empty())
    	{
    		if(root != NULL)
    		{
    			//cout<<root->value<<endl;
    			if(root->value == part->value && IsSame(root,part))
    				return true;
    			st.push(root);
    			root = root->left;
    		}
    		else
    		{
    			root = st.top();
    			st.pop();
    			root = root->right;
    		}
    	}
    	return false;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，153人围观）

还没有评论，来说两句吧...

相关阅读

相关判断一棵树是否是另一棵树的子树（Java实现）

前面一篇文章介绍了如何判断两棵树相等，思路就是遍历每个节点，然后判断是否均相等，需要用递归来实现。如果需要判断一棵树是另一棵树的子树，该怎么办呢？我们需要借助前面的...

谁借莪１个温暖的怀抱￠/ 2024年04月19日 16:32/ 0 赞/ 62 阅读

相关 LeetCode-572. 另一棵树的子树

题目来源 [572. 另一棵树的子树][572.] 解题思路看到题目描述，首先判断一个树是否是另一棵树的子树，很明显想到可以用递归，但是两棵树完全相同也可以看做一

柔情只为你懂/ 2024年03月27日 15:55/ 0 赞/ 71 阅读

相关 java判断一棵二叉树是另一棵二叉树的子树

判断一棵二叉树是另一棵二叉树的子树题目描述给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子

àì夳堔傛蜴生んèń/ 2024年03月16日 10:51/ 0 赞/ 82 阅读

相关 Java另一棵树的子树

目录 1.题目描述 2.题解思路分析具体实现完整代码 -------------------- 1.题目描述给你两棵二叉树 `root`和 `sub

男娘i/ 2024年02月24日 08:13/ 0 赞/ 40 阅读

相关另一颗树的子树（数据结构基础回顾）

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

末蓝、/ 2023年02月23日 12:09/ 0 赞/ 1 阅读

相关 Leetcode 572. 另一棵树的子树

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

Myth丶恋晨/ 2022年09月16日 11:24/ 0 赞/ 144 阅读

相关 572 另一棵树的子树（树的哈希）

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

以你之姓@/ 2022年08月31日 11:06/ 0 赞/ 165 阅读

相关判断树为另一树的子结构

输入两棵二叉树 A 和 B，判断树 B 是不是 A 的子结构。例如，下图中的两棵树 A 和 B，由于 A 中有一部分子树的结构和 B 是一样的，因此 B 就是 A

缺乏、安全感/ 2022年08月08日 00:58/ 0 赞/ 154 阅读

相关如何判断一棵树是不是另一棵树的子树

给你两棵树，怎么判断一棵树是另一棵树的子树？树1：树2: 1 2 / \\ / \\ 2 3 4 5 / \\ \\ 4 5 7 第一步

红太狼/ 2022年06月07日 23:46/ 0 赞/ 242 阅读

相关判断一颗二叉树是否是另一颗树的子树。

思路：首先找到值相同的根节点，然后递归判断是否完全相同。（方便起见，样例还是建一个二叉搜索树） include <bits/stdc++.h> usin

冷不防/ 2022年04月18日 01:56/ 0 赞/ 191 阅读