剑指offer第二版-26.树的子结构

本系列导航：剑指offer（第二版）java实现导航帖

面试题25：树的子结构

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

解题思路：
当A有一个节点与B的根节点值相同时，则需要从A的那个节点开始严格匹配，对应于下面的tree1HasTree2FromRoot函数。如果匹配不成功，则返回到开始匹配的那个节点，对它的左右子树继续判断是否与B的根节点值相同，重复上述过程。

package structure;
/**
 * Created by ryder on 2017/6/12.
 * 树节点
 */
public class TreeNode<T> {
    public T val;
    public TreeNode<T> left;
    public TreeNode<T> right;
    public TreeNode(T val){
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

package chapter3;
import structure.TreeNode;
/**
 * Created by ryder on 2017/7/14.
 * 树的子结构
 */
public class P148_SubstructureInTree {
    public static boolean hasSubtree(TreeNode<Integer> root1, TreeNode<Integer> root2){
        if(root2==null)
            return true;
        if(root1==null)
            return false;
        if(root1.val.equals(root2.val)){
            if(tree1HasTree2FromRoot(root1,root2))
                return true;
        }
        return hasSubtree(root1.left,root2) || hasSubtree(root1.right,root2);
    }
    public static boolean tree1HasTree2FromRoot(TreeNode<Integer> root1, TreeNode<Integer> root2){
        if(root2==null)
            return true;
        if(root1==null)
            return false;
        if(root1.val.equals(root2.val) && tree1HasTree2FromRoot(root1.left,root2.left) && tree1HasTree2FromRoot(root1.right,root2.right))
            return true;
        else
            return false;

    }
    public static void main(String[] args){
        TreeNode<Integer> root1 = new TreeNode<>(8);
        root1.left = new TreeNode<>(8);
        root1.right = new TreeNode<>(7);
        root1.left.left = new TreeNode<>(9);
        root1.left.right = new TreeNode<>(2);
        root1.left.right.left = new TreeNode<>(4);
        root1.left.right.right = new TreeNode<>(7);
        TreeNode<Integer> root2 = new TreeNode<>(8);
        root2.left = new TreeNode<>(9);
        root2.right = new TreeNode<>(2);
        TreeNode<Integer> root3 = new TreeNode<>(2);
        root3.left = new TreeNode<>(4);
        root3.right = new TreeNode<>(3);
        System.out.println(hasSubtree(root1,root2));
        System.out.println(hasSubtree(root1,root3));
    }
}

运行结果

true
false