首页 > 试题广场 > 树的子结构
[编程题]树的子结构
  • 热度指数:780883 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
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);
    }

发表于 2016-08-23 12:02:39 回复(85)
利用好短路特性,完全不用那么多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 回复(127)
/*思路:参考剑指offer
1、首先设置标志位result = false,因为一旦匹配成功result就设为true,
剩下的代码不会执行,如果匹配不成功,默认返回false
2、递归思想,如果根节点相同则递归调用DoesTree1HaveTree2(),
如果根节点不相同,则判断tree1的左子树和tree2是否相同,
再判断右子树和tree2是否相同
3、注意null的条件,HasSubTree中,如果两棵树都不为空才进行判断,
DoesTree1HasTree2中,如果Tree2为空,则说明第二棵树遍历完了,即匹配成功,
tree1为空有两种情况(1)如果tree1为空&&tree2不为空说明不匹配,
(2)如果tree1为空,tree2为空,说明匹配。

*/

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean result = false;
	        if(root1 != null && root2 != null){
	        	if(root1.val == root2.val){
	        		result = DoesTree1HaveTree2(root1,root2);
	        	}
	        	if(!result){result = HasSubtree(root1.left, root2);}
	        	if(!result){result = HasSubtree(root1.right, root2);}
	        }
	        return result;
    }
    public boolean DoesTree1HaveTree2(TreeNode root1,TreeNode root2){
	    	if(root1 == null && root2 != null) return false;
	    	if(root2 == null) return true;
	    	if(root1.val != root2.val) return false;
	    	return DoesTree1HaveTree2(root1.left, root2.left) && DoesTree1HaveTree2(root1.right, root2.right);
	    }
}

编辑于 2016-05-12 21:47:46 回复(18)

对于Python这道题,有些地方需要仔细考虑的。

先说下算法实现思路:对于两棵二叉树来说,要判断B是不是A的子结构,首先第一步在树A中查找与B根节点的值一样的节点。

通常对于查找树中某一个节点,我们都是采用递归的方法来遍历整棵树。

第二步就是判断树A中以R为根节点的子树是不是和树B具有相同的结构。

这里同样利用到了递归的方法,如果节点R的值和树的根节点不相同,则以R为根节点的子树和树B肯定不具有相同的节点;

如果它们值是相同的,则递归的判断各自的左右节点的值是不是相同。

递归的终止条件是我们达到了树A或者树B的叶节点。

有地方要重点注意,DoesTree1haveTree2()函数中的两个 if 判断语句 不能颠倒顺序
因为如果颠倒了顺序,会先判断pRoot1 是否为None, 其实这个时候,pRoot1 的节点已经遍历完成确认相等了,但是这个时候会返回 False,判断错误。

有同学不相信的,可以去试试换个顺序,肯定不能AC。同时这个也是《剑指offer》书上没有写的,希望能引起大家的注意。
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        result = False
        if pRoot1 != None and pRoot2 != None:
            if pRoot1.val == pRoot2.val:
                result = self.DoesTree1haveTree2(pRoot1, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.left, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.right, pRoot2)
        return result
    # 用于递归判断树的每个节点是否相同
    # 需要注意的地方是: 前两个if语句不可以颠倒顺序
    # 如果颠倒顺序, 会先判断pRoot1是否为None, 其实这个时候pRoot2的结点已经遍历完成确定相等了, 但是返回了False, 判断错误
    def DoesTree1haveTree2(self, pRoot1, pRoot2):
        if pRoot2 == None:
            return True
        if pRoot1 == None:
            return False
        if pRoot1.val != pRoot2.val:
            return False
        return self.DoesTree1haveTree2(pRoot1.left, pRoot2.left) and self.DoesTree1haveTree2(pRoot1.right, pRoot2.right)
发表于 2017-07-22 12:42:02 回复(24)
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(pRoot2 == NULL || pRoot1 == NULL )
            return false;
        return isSubtree(pRoot1, pRoot2)|| HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right,pRoot2);
    }
     
    bool isSubtree(TreeNode* pRoot1 , TreeNode* pRoot2){
        if(pRoot2 == NULL)
            return true;
        if(pRoot1 == NULL)
            return false;
        return pRoot1->val == pRoot2->val && isSubtree(pRoot1->left,pRoot2->left) && isSubtree(pRoot1->right,pRoot2->right);
    }
};

发表于 2015-08-12 15:55:05 回复(20)
思路:对A树DFS,如果B的根节点与A中某个节点值相同,那么以B为树根进行DFS,判断即可
时间复杂度为O(n * m)

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

编辑于 2016-07-29 16:03:39 回复(27)
Java版本
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    if(root1==null || root2==null)  return false;
    return doesTree1HasTree2(root1, root2)|| HasSubtree(root1.left, root2)
            ||HasSubtree(root1.right, root2);
}

private boolean doesTree1HasTree2(TreeNode root1,TreeNode root2) {
    if(root2==null)  return true;
    if(root1==null)  return false;
    return root1.val==root2.val && doesTree1HasTree2(root1.left, root2.left)
            && doesTree1HasTree2(root1.right, root2.right);
}

编辑于 2018-10-16 15:50:34 回复(5)
python solution
-*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        result = False
        if  pRoot1 and  pRoot2:
            if pRoot1.val==pRoot2.val:
                result = self.DoesTree1HaveTree2(pRoot1,pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.left,pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.right,pRoot2)
        return result
    
    def DoesTree1HaveTree2(self,pRoot_A,pRoot_B):
        if not pRoot_B:
            return True
        if not pRoot_A:
            return False
        if pRoot_A.val != pRoot_B.val:
            return False
        
        return self.DoesTree1HaveTree2(pRoot_A.left,pRoot_B.left) and self.DoesTree1HaveTree2(pRoot_A.right,pRoot_B.right)

参考剑指Offer书中思路,用Python写的
在上述代码中,我们递归调用HasSubtree遍历二叉树A。如果发现某一节点的值和树B的根结点的值相等,则调用DoesTree1HaveTree2,进行第二步判断。
第二步是判断树A中以R为跟结点的子树是不是和树B具有相同的结构。同样,我们也可以用递归的思路来考虑:如果节点R的值和树B的根节点不同,那么以R为根节点的子树和树B肯定不具有相同的节点;如果它们的值相同,那么递归地判断它们各自的左右节点的值是不是相同。递归的终止条件是到达了树A或者树B的叶子节点。
  需要注意的是  DoesTree1HasTree2函数中,如果Tree2为空,则说明第二棵树遍历完了,即是第一颗树的子树,返回TRUE
   如果tree1为空而tree2不为空说明tree2结构超大,tree1中不存在



编辑于 2019-05-21 23:19:17 回复(1)
重新整理了代码,注释写的非常清楚了,欢迎讨论和代码给出意见
思考:
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)

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)
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)
先把两个树转化成先序遍历的字符串,然后判断第二个字符串是不是第一个的子字符串
# -*- 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)
function HasSubtree(pRoot1, pRoot2)
{
    if (!pRoot2) {
        return false;
    }
    
    return preOrder(pRoot1).includes(preOrder(pRoot2));
}

function preOrder(root) {
    let val = [];

    (function handle(root) {
        if (root) {
            val.push(root.val);
            handle(root.left);
            handle(root.right);
        }
    })(root);
    
    return val.join(',');
}
通过先序遍历判断子集
发表于 2018-08-26 20:59:12 回复(2)
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)
关于先序遍历包含关系判断子树
如下图:分别对三棵树进行先序遍历,TreeA{1,2,4,5,3},TressB{1,2,4},TreeC{4,5,3},可以看出虽然子序列有包含关系,但并不是子树。
编辑于 2017-04-11 10:47:42 回复(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)
这题必须用暴力,也就是尝试用第一棵树的每个节点,和第二棵树比较,直到找到与第二棵树相同的子结构。时间复杂度为O(mn)
任何通过先中后序遍历序列是否吻合进行判断的算法都是错的。可以很容易的举出反例,假设两棵树的节点值完全一样,则无论任何方法遍历出的结果都完全相同。而结构却可以不同。
发表于 2019-04-10 04:24:41 回复(0)