首页 > 试题广场 >

树的子结构

[编程题]树的子结构
  • 热度指数:942954 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
输入两棵二叉树A,B,判断B是不是A的子结构。(我们约定空树不是任意一个树的子结构)
假如给定A为{8,8,7,9,2,#,#,#,#,4,7},B为{8,9,2},2个树的结构如下,可以看出B是A的子结构

数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000
示例1

输入

{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}

输出

true
示例2

输入

{1,2,3,4,5},{2,4}

输出

true
示例3

输入

{1,2,3},{3,1}

输出

false

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
思路:对A树DFS,如果B的根节点与A中某个节点值相同,那么以B为树根进行DFS,判断即可
时间复杂度为O(n * m)

ps:
看到有人提出了KMP的想法,即先序遍历然后比较B的先序序列是否是A的先序序列的子序列
时间复杂度O(n + m),想法挺好的,但是要考虑下面这种情况是否满足题意。如果下列满足
题意,那么使用这种方法是不对的。

编辑于 2016-07-29 16:03:39 回复(29)

python solution:

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        
        def convert(p):
            if p:
                return str(p.val) +  convert(p.left) + convert(p.right)
            else:
                return ""
        return convert(pRoot2) in convert(pRoot1) if pRoot2 else False
编辑于 2017-10-14 14:04:19 回复(32)
重新整理了代码,注释写的非常清楚了,欢迎讨论和代码给出意见
思考:
1.首先需要递归pRoot1树,找到与pRoot2根一样的节点,这需要一个遍历
2.找到相同的根节点后,要判断是否子树,仍需要一个一个遍历对比
树的遍历我们一般就用递归来做,那么根据分析需要两个递归函数如下:
bool IsSubtree(TreeNode*p1, TreeNode *p2)
{
    if (!p2)
 	//此处为p2 == null 是匹配完成的条件
    //最开始p2肯定不为NULL,这是在主程序HasSubtree中判断过的。
    //递归中,如果p2为空了,则表示上一层的递归中的p2已经匹配完了
		return true;
	if (!p1)
		return false;


	if (p1->val != p2->val)
		return false;

	return IsSubtree(p1->left, p2->left) && IsSubtree(p1->right, p2->right);

}

bool HasSubtree(TreeNode *pRoot1, TreeNode *pRoot2)
{
	if(pRoot2 == nullptr)
        return false;//题目要求,空树不是任何树的子结构
	if(pRoot1 == nullptr)
        return false; //显然
	
    //return IsSubtree(pRoot1, pRoot2)||HasSubtree(pRoot1->left, pRoot2)|| HasSubtree(pRoot1->right, pRoot2);
    //为了思路清楚,分开谢了,可以利用||或运算直接return
    
	bool flag = IsSubtree(pRoot1, pRoot2);//看看B是不是以A的根为根的子结构
	if (!flag)//递归A的左子树,看看做子树中有没有B子结构
		flag = HasSubtree(pRoot1->left, pRoot2);
	if (!flag)//同上,递归A的右子树
		flag = HasSubtree(pRoot1->right, pRoot2);

	return flag;
}

其中需要注意的是:
1. 测试用例如果pRoot2为空的话,返回的false而不是我们认为的空树应该是所有树的子树
2. 再判断是否子树的过程中,应该先判断pRoot2是否为空,为空则表明子树的所有节点都比较完了,应该是子树返回True
3. 要养成一个习惯,对任何一个树节点进行访问时,一定要提前检测该节点是否为空
编辑于 2016-08-22 23:00:35 回复(9)
public boolean IsSubtree(TreeNode root1, TreeNode root2){
		if(root2 == null)
			return true;
		if(root1 == null)
			return false;
		if(root1.val == root2.val)
		return IsSubtree(root1.left,root2.left) && IsSubtree(root1.right, root2.right);
		else return false;
	}
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null)
        	return false;
        return IsSubtree(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

发表于 2016-08-25 19:22:55 回复(4)
/*public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}*/
public class Solution {
   public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2==null) return false;
        if(root1==null && root2!=null) return false;        
        boolean flag = false;
        if(root1.val==root2.val){
            flag = isSubTree(root1,root2);
        }
        if(!flag){
            flag = HasSubtree(root1.left, root2);
            if(!flag){
                flag = HasSubtree(root1.right, root2);
            }
        }
        return flag;
    }
    
    private boolean isSubTree(TreeNode root1, TreeNode root2) {
        if(root2==null) return true;
        if(root1==null && root2!=null) return false;        
        if(root1.val==root2.val){
            return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
        }
        return false;
    }
}

发表于 2015-04-11 13:50:35 回复(6)
public class Solution {
    public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
		boolean result = false;
		//当Tree1和Tree2都不为零的时候,才进行比较。否则直接返回false
		if (root2 != null && root1 != null) {
			//如果找到了对应Tree2的根节点的点
			if(root1.val == root2.val){
				//以这个根节点为为起点判断是否包含Tree2
				result = doesTree1HaveTree2(root1,root2);
			}
			//如果找不到,那么就再去root的左儿子当作起点,去判断时候包含Tree2
			if (!result) {
				result = HasSubtree(root1.left,root2);
			}
			
			//如果还找不到,那么就再去root的右儿子当作起点,去判断时候包含Tree2
			if (!result) {
				result = HasSubtree(root1.right,root2);
			   }
			}
		    //返回结果
		return result;
	}

	public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
		//如果Tree2已经遍历完了都能对应的上,返回true
		if (node2 == null) {
			return true;
		}
		//如果Tree2还没有遍历完,Tree1却遍历完了。返回false
		if (node1 == null) {
			return false;
		}
		//如果其中有一个点没有对应上,返回false
    	if (node1.val != node2.val) {	
				return false;
		}
    	
    	//如果根节点对应的上,那么就分别去子节点里面匹配
    	return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
    }
}

编辑于 2021-03-06 10:26:13 回复(90)
先把两个树转化成先序遍历的字符串,然后判断第二个字符串是不是第一个的子字符串
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def tree2str(self,root):
        if not root:
            return ''
        re = ''
        re+=str(root.val)
        if root.left or  root.right:
            re += self.tree2str(root.left) + self.tree2str(root.right)
        return re

    def HasSubtree(self, pRoot1, pRoot2):
        if not pRoot2:
            return False
        str1 = self.tree2str(pRoot1)
        str2 = self.tree2str(pRoot2)
        if str1.find(str2) == -1:
            return False
        else:
            return True

发表于 2017-08-28 20:16:48 回复(6)
利用好短路特性,完全不用那么多flag

class Solution {
    bool isSubtree(TreeNode* pRootA, TreeNode* pRootB) {
        if (pRootB == NULL) return true;
        if (pRootA == NULL) return false;
        if (pRootB->val == pRootA->val) {
            return isSubtree(pRootA->left, pRootB->left)
                && isSubtree(pRootA->right, pRootB->right);
        } else return false;
    }
public:
    bool HasSubtree(TreeNode* pRootA, TreeNode* pRootB)
    {
        if (pRootA == NULL || pRootB == NULL) return false;
        return isSubtree(pRootA, pRootB) ||
            HasSubtree(pRootA->left, pRootB) ||
            HasSubtree(pRootA->right, pRootB);
    }
};

发表于 2015-07-27 20:23:22 回复(129)
class Solution {
public:
	bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
	{
		if (pRoot2 == NULL || pRoot1 == NULL) return false; 
		return dfs(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2)
			|| HasSubtree(pRoot1->right, pRoot2);
	}
	bool dfs(TreeNode* node, TreeNode* pRoot2) {
		if (pRoot2 == NULL) return true;
		else if (node != NULL) {
			return (node->val == pRoot2->val) && dfs(node->left, pRoot2->left)
				&& dfs(node->right, pRoot2->right);
		}
		else return false;
	}
};

发表于 2017-07-20 15:30:28 回复(0)
public class Solution {


    public boolean HasSubtree(TreeNode tree, TreeNode sub) {
        return sub == null ? false : isSubtree(tree, sub);
    }

    private boolean isSubtree(TreeNode tree, TreeNode sub) {
        if (sub == null) return true;
        if (tree == null) return false;

        if (tree.val == sub.val) {
            boolean isSameTree = isSubtree(tree.left, sub.left) && isSubtree(tree.right, sub.right);
            if (isSameTree) return true;
        }
        return isSubtree(tree.left, sub) || isSubtree(tree.right, sub);
    }
}
编辑于 2019-04-23 17:54:58 回复(2)
解题思路:
1.找到A中和B的根节点相同的节点,然后进行判断是否相同。
2.如果不同再拿A的左子树和B进行比较。
3.如果仍不同再拿A的右子树与B进行比较。
4.如果仍未找到,则A中不包含B。
判断两个根节点相同的两个树是否包含:
1.先判断B,如果B为空说明包含。
2.再判断A,如果A为空就说明不包含。
3.如果A的值与B的值相同,然后继续进行此判断。
发表于 2019-04-21 22:13:41 回复(0)
    /* 改进算法,时间复杂度O(m+n)
     * 1.将root1和root2分别按先序遍历序列化。
     * 2.运用KMP算法匹配序列化结果。
     */
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    	if(root2==null)
    		return false;// 空树本应是任意树的子结构,但从测试集来看,应视为false
    	if(root1==null)
    		return false;
    	char[] str = Serialize(root1).toCharArray();
    	char[] pattern = Serialize(root2).toCharArray();
    	int[] next = new int[pattern.length];
    	System.out.println(String.valueOf(str));
    	System.out.println(String.valueOf(pattern));
    	getNext(pattern,next);
		return KMP(str,pattern,next);
        
    }
	private boolean KMP(char[] str, char[] pattern, int[] next) {
		if(str==null||pattern==null)
			return false;
		if(str.length<pattern.length)
			return false;
		int i=0,j=0,len = str.length;
		while(i<len&&j<pattern.length){
			if(j==-1||str[i]==pattern[j]){
				i++;j++;
			}else{
				j = next[j];
			}
		}
		if(j==pattern.length)// 表示最后一个字符也相等,匹配成功
			return true;
		return false;
	}

	private void getNext(char[] pattern, int[] next) {
		if(pattern==null||pattern.length==0)
			return;
		int i=0,j=-1;
		next[0] = -1;
		while(i<pattern.length-1){
			if(j==-1||pattern[i]==pattern[j]){
				++i;++j;				
				if(pattern[i]==pattern[j]){
					next[i] = next[j];
				}else{
					next[i] = j;
				}
			}else{
				j = next[j];
			}
		}
	}
	public String Serialize(TreeNode root) {
		if(root==null)
			return "";
		this.buffer = new StringBuffer();
		SerializeF(root);
		int i;
		// 删除序列尾部的$
		for(i = buffer.length()-1;i>=0;i--){
			if(buffer.charAt(i)==','||buffer.charAt(i)=='$'){
				continue;
			}else
				break;
		}
		buffer.delete(i+1,buffer.length());
		return buffer.toString();
	}

编辑于 2015-08-13 14:39:39 回复(10)
1.非递归
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool isSub(TreeNode* p1, TreeNode* p2){
        //非递归
        if (!p2) return true;
        if (!p1) return false;
        return p1->val == p2->val && isSub(p1->left, p2->left) && isSub(p1->right, p2->right);
    }
    //中序遍历
    bool HasSubtree(TreeNode* p1, TreeNode* p2) {
        if(!p2) return false;
        stack<TreeNode*> st;
        while(p1||!st.empty()){
            while(p1){
                if(p1->val==p2->val&&isSub(p1, p2))
                    return true;
                st.push(p1);
                p1=p1->left;
            }
            TreeNode* t=st.top();
            st.pop();
            p1=t->right;
        }
        return false;

    }
};
2. 递归
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool isSub(TreeNode* p1, TreeNode* p2) {
        //递归
        if(!p2)
            return true;
        else if(!p1)
            return false;
        
        return p1->val==p2->val&&isSub(p1->left, p2->left)&&isSub(p1->right, p2->right);
        
    }
    bool HasSubtree(TreeNode* p1, TreeNode* p2) {
        if(!p1||!p2)
            return false;
        
        return isSub(p1, p2)||HasSubtree(p1->left, p2)||HasSubtree(p1->right, p2);
    
    
    
    }

};



发表于 2021-09-09 10:50:59 回复(0)
整体分为两步
第一步:在root1上找和root2相同值的节点。
第二部:判断root2是否是该节点的子结构。
递归的在root1.left和root2.rigth子树上找。任意一个子树满足就返回true
public class Solution {
    //使用该方法在root1上找与root2值相同的节点。
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        //当root1和root2中由任意一个是空的话,那直接返回false
        if(root1 == null || root2 == null) return false;
        //首先是要找到相同值的节点,然后从该节点判断root2是否是该节点的子结构
        if(root1.val == root2.val){
            //这里不是直接返回是否是子结构的判断结果,如果是直接返回判断结果的话则只是对一个节点上做了判断,没有向下继续判断
            //这里是先判断当前是否是子结构,然后是子结构才返回true。不是子结构就去继续判断root1的左右子节点。
            if(subTree(root1,root2)){
                return true;
            }
        }
        //当前节点不满足再使用它的左右子节点递归判断。只要由一个子树包含root2树,即可返回true,故用||
        return HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
    }
    
    //判断root2是否是root1的子结构
    public boolean subTree(TreeNode root1,TreeNode root2){
        //当root2每个节点都判断完毕了,说明root2是root1的子结构
        if(root2 == null) return true;
        //当roo2没判断完,而root1已经判断完了,说明root2不是root1的子结构
        if(root1 == null) return false;
        //如果当前root1和root2的节点值相等,那么在去判断两者的子树。
        if(root1.val == root2.val){
            return subTree(root1.left,root2.left)&&subTree(root1.right,root2.right);
        }
        //反之root1.val和root2.val的值不相等,直接返回false
        return false;
    }
    
}


发表于 2021-08-07 08:46:24 回复(0)
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        return (root1!=null&&root2!=null)&&
            (recur(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2));
    }
    boolean recur(TreeNode A,TreeNode B){
        if(B==null)return true;//说明匹配完成 B是A的子结构
        if(A==null||A.val!=B.val)return false;//A树为空或者节点值不相等 说明不是子结构
        return recur(A.left,B.left)&&recur(A.right,B.right);
    }
}

发表于 2021-07-31 19:45:26 回复(0)
//Javascript 描述,用flag表示函数状态。
function HasSubtree(p1, p2,flag)
{
    var f=HasSubtree;
    if(flag && !p2) return true;
    if(!p1 || !p2) return false;
    if(p1 && p2 && p1.val == p2.val) 
        return f(p1.left,p2.left,true) && f(p1.right,p2.right,true) || f(p1.left,p2)||f(p1.right,p2);
    return  f(p1.left,p2) || f(p1.right,p2);
}

编辑于 2017-09-19 22:15:03 回复(0)
对每一个结点判断是否是子🌲, 其中isSubtree用来判断t1和t2是否是相同子树。
  1. 当t2==NULL时说明能够遍历到叶子,则t2是t1子树。
  2. 当t1==NULL&&t2!=NULL则t2还没遍历完,t1就结束了,那么肯定不是子树。
  3. 如果这两个结点t1 t2的值相同,则要比较他们的左右子树,只要有一个子树不同那么就没有父子关系。
  4. 如果值不相同直接返回FALSE;
用HasSubtree来选择哪两个结点来进行选择。
  1. 只要两个结点有一个是空结点,不需要比较,返回NULL。
  2. 这个结点或者这个结点的左右子树,只要有一个满足与被比较结点是有相同的子树(也就是返回true)那么就应该返回true作为结果。
class Solution {
public:
    bool isSubtree(TreeNode *t1, TreeNode *t2){
        if(t2==NULL) return true;
        if(t1==NULL && t2!=NULL) return false;
        if(t1->val == t2->val){
            bool lTree = isSubtree(t1->left, t2->left);
            bool rTree = isSubtree(t1->right, t2->right);
            return lTree && rTree;
        }else return false;
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
		if(pRoot1 == NULL || pRoot2 == NULL) return false;
        return isSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2)
            || HasSubtree(pRoot1->right, pRoot2);
    }
};

发表于 2017-03-10 18:24:14 回复(0)
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
		if(root2 == null) {
			return false;
		}
		List<TreeNode> list1 = new ArrayList<>();
		List<TreeNode> list2 = new ArrayList<>();
		preOrderTraversal(root1, list1);
		preOrderTraversal(root2, list2);
		StringBuffer sb1 = new StringBuffer();
		for (int i = 0; i < list1.size(); i++) {
			sb1.append(list1.get(i).val);
		}
		StringBuffer sb2 = new StringBuffer();
		for(int i = 0; i < list2.size(); i++) {
			sb2.append(list2.get(i).val);
		}
		return sb1.toString().indexOf(sb2.toString()) >= 0 ? true : false;
//		return !list1.contains(list2);	//是错误的做法,contains只能检测一个list钟是否包含某元素
	}
	
	public void preOrderTraversal(TreeNode root, List<TreeNode> list) {
		if(root == null) {
			return;
		}
		list.add(root);
		preOrderTraversal(root.left, list);
		preOrderTraversal(root.right, list);
	}

发表于 2016-12-14 14:25:35 回复(6)
class Solution {
public:
//递归判断,分条件
    bool HasSubtree(TreeNode* p1, TreeNode* p2)
    {
	    if(p1==NULL||p2==NULL) return false;
    	return Hbtree(p1,p2);
	}
    bool Hbtree(TreeNode* p1, TreeNode* p2)
    {
		if(p2==NULL) return true;
        if(p1==NULL) return false;
        if(p1->val==p2->val)
        {
             if(Hbtree(p1->left,p2->left)&&Hbtree(p1->right,p2->right)) return true;
		}

        return Hbtree(p1->left,p2)||Hbtree(p1->right,p2);      
    }
};

发表于 2016-08-15 00:58:43 回复(1)
我觉得就是做一个遍历,比如做前序遍历,获取到遍历的序列,看看A的遍历序列是否包含B的遍历序列
发表于 2015-04-15 20:50:38 回复(24)