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

谁借莪１个温暖的怀抱￠ 2024-04-19 16:32 68阅读 0赞

前面一篇文章介绍了如何判断两棵树相等，思路就是遍历每个节点，然后判断是否均相等，需要用递归来实现。如果需要判断一棵树是另一棵树的子树，该怎么办呢？我们需要借助前面的思路，需要先判断两棵树相等，这里就是判断一棵树是另一棵树的一部分，也就是说如果是子树，那么这棵小树肯定是这棵大树某一个节点的子节点以及子孙节点组成的一部分。可以用到前面判断相等的方法。假定我们有两棵树的根节点，分别为t1,t2，如果我们判断t1.left和t2是相等的，或者是t1.right和t2是相等的，那么可以判断t2就是t1的子树。

按照上面的思路，我们可以写出这样的程序。

package com.xxx.algorithm.wh;
    public class Tree {
    	public static class TreeNode{
    		int data;
    		public TreeNode(int data) {
    			this.data = data;
    			this.left = null;
    			this.right = null;
    		}
    		TreeNode left;
    		TreeNode right;
    	}
    	
    	public static boolean equals(TreeNode t1,TreeNode t2){
    		if(t1==null&&t2==null)
    			return true;
    		if(t1==null||t2==null)
    			return false;
    		return t1.data==t2.data && equals(t1.left, t2.left) && equals(t1.right, t2.right);
    	}
    	
    	public static boolean subTree(TreeNode t1,TreeNode t2){
    		if(t1==null)return false;
    		if(equals(t1, t2))return true;
    		return subTree(t1.left, t2) || subTree(t1.right, t2);
    	}
    	
    	public static void main(String[] args) {
    		//      a            b
    		//------------------------
    		//      10
    		//     /  \
    		//    9    8          9
    		//   / \             / \
    		//  7   6           7   6
    		TreeNode a1 = new TreeNode(10);
    		TreeNode a2 = new TreeNode(9);
    		TreeNode a3 = new TreeNode(8);
    		TreeNode a4 = new TreeNode(7);
    		TreeNode a5 = new TreeNode(6);
    		a1.left = a2;
    		a1.right = a3;
    		a2.left = a4;
    		a2.right = a5;
    		
    		TreeNode b1 = new TreeNode(9);
    		TreeNode b2 = new TreeNode(7);
    		TreeNode b3 = new TreeNode(6);
    		b1.left = b2;
    		b1.right = b3;
    		
    		System.out.println("subTree(a,b)="+subTree(a1, b1));
    		
    	}
    	
    }

运行程序，打印信息如下：

subTree(a,b)=true

这里我们直接通过节点之间的关系构建了两棵树，分别是a,b，b是a的根节点的左子树，这里通过程序代码判断，是正确的，如果我们修改节点，那么判断就会返回假：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/584d4dc78e364f2b92cc6d8214846a07.png