【Java】剑指offer树的子结构

左手的ㄟ右手 2022-01-28 01:25 163阅读 0赞

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

package 牛客;
    
    public class TreeNode {
        
    	    int val = 0;
    	    TreeNode left = null;
    	    TreeNode right = null;
    
    	    public TreeNode(int val) {
        
    	        this.val = val;
    
    	    }
    
    }

主思想采用递归实现遍历二叉树，从根节点开始判断。  
如果根节点相同则递归调用panduan（），  
如果根节点不相同，则判断tree1的左子树和tree2是否相同，  
再判断右子树和tree2是否相同。

package 牛客;
    
    
    
    public class 树的子结构 {
        
    	public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
        
    		boolean result = false;//设result=false,一旦匹配成功返回true，否则返回false
    		if (root2 != null && root1 != null) {
        //先判断是否为空
    			if (root1.val == root2.val) {
        //先找能对应的根节点
               result = panduan(root1, root2);// 以这个根节点为为起点判断是否包含Tree2
    			}
    			// 如果找不到，那么就再去root的左子树当作起点，去判断时候包含Tree2
    			if (!result) {
        
    				result = HasSubtree(root1.left, root2);
    			}
    
    			// 如果还找不到，那么就再去root的右子树当作起点，去判断时候包含Tree2
    			if (!result) {
        
    				result = HasSubtree(root1.right, root2);
    			}
    		}
    		return result;
    	}
    
    	public static boolean panduan(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 panduan(node1.left, node2.left) && panduan(node1.right, node2.right);
    	}
    }