26:树的子结构

题目26：树的子结构

输入两棵二叉树A 和B，判断B 是不是A 的子结构。

举例说明

思路

和二叉树有关的问题，很多都可以递归解决，因为子问题和本问题具有一致性。关键是问题的划分和base case。

本题现在A中找出所有和B根节点一样的节点R

步骤

要查找树A 中是否存在和树B 结构一样的子树，我们可以分成两步

1. 在树A 中找到和B 的根结点的值一样的结点R
2. 判断树A 中以R 为根结点的子树是不是包含和树B 一样的结构

代码实现

public class _26 {
	public static class BinaryTreeNode {
		int value;//若果是double，比较相等就重写equals(),而不是直接"=="
		BinaryTreeNode left;
		BinaryTreeNode right;

		public BinaryTreeNode() {
		}
		public BinaryTreeNode(int value) {
			this.value = value;
		}
	}
	
    public static boolean hasSubtree(BinaryTreeNode root1, BinaryTreeNode root2) {       
        if (root1 == root2) {//自反性
            return true;
        }
        if (root2 == null) {//null节点 是任意树的 子树（null节点是所有叶子节点的子节点）
            return true;
        }
        if (root1 == null) {//已经排除了root2==null
            return false;
        }

        boolean result = false;// 记录匹配结果
        if (root1.value == root2.value) {// 如果结点的值相等就，调用匹配方法
            result = isSubtree(root1, root2);// call rescursive
        }      
        if (result) {
            return true;// 如果匹配就直接返回结果，不在遍历A寻找和root2等值的节点
        }
        // 如果不匹配，遍历A，找到和root2等值的节点，进行判断
        return hasSubtree(root1.left, root2) || hasSubtree(root1.right, root2);
    }

    //从树A根结点root1和树B根结点root2开始，一个一个元素进行判断，判断B是不是A的子结构
    public static boolean isSubtree(BinaryTreeNode root1, BinaryTreeNode root2) {
        if (root1 == root2) {//自反性
            return true;
        }
        if (root2 == null) {//null节点 是任意树的 子树（null节点是所有叶子节点的子节点）
            return true;
        }
        if (root1 == null) {//已经排除了root2==null
            return false;
        }
        // 如果两个结点的值相等，递归判断其左子结点和右子结点
        if (root1.value == root2.value) {
            return isSubtree(root1.left, root2.left) && isSubtree(root1.right, root2.right);
        }
        return false;// 结点值不相等返回false
    }

    public static void main(String[] args) {
//        8
//      /  \
//     6    10
//    / \   / \
//   5  7   9 11
		BinaryTreeNode root1 = new BinaryTreeNode(8);
		BinaryTreeNode n2 = new BinaryTreeNode(6);
		BinaryTreeNode n3 = new BinaryTreeNode(10);
		BinaryTreeNode n4 = new BinaryTreeNode(5);
		BinaryTreeNode n5 = new BinaryTreeNode(7);
		BinaryTreeNode n6 = new BinaryTreeNode(9);
		BinaryTreeNode n7 = new BinaryTreeNode(11);
		root1.left = n2;
		root1.right = n3;
		n2.left = n4;
		n2.right = n5;
		n3.left = n6;
		n3.right = n7;
//	     6    
//	    / \   
//     5   7
        BinaryTreeNode root2 = new BinaryTreeNode(6);
		BinaryTreeNode n8 = new BinaryTreeNode(5);
		BinaryTreeNode n9 = new BinaryTreeNode(7);
		root2.left = n8;
		root2.right = n9;

        System.out.println(hasSubtree(root1, root2));//true
        System.out.println(hasSubtree(root1, null));//true
        System.out.println(hasSubtree(null, root2));//false
        System.out.println(hasSubtree(null, null));//true
    }
}

输出：

true
true
false
true