树的子结构

题目描述

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

题解

树的遍历有递归和迭代

递归比较容易写，就递归吧

先在A树中递归查找B树的根节点

找到后，再递归判断两颗树的左右孩子是否相等，都相等则B是A的子结构

不等，继续在A中找下一个B的根节点

/*判断root2是否是root1的子树*/
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
    if (root1 == null || root2 == null)
        return false;

    boolean res = false;

    /*
    在Tree1中找Tree2的根节点
    */

    //找到了，就去判断它们的左右孩子是否相等
    if (root1.val == root2.val)
        res = HasNode(root1,root2);

    if (!res)
        res = HasSubtree(root1.left,root2);
    if (!res)
        res = HasSubtree(root1.right,root2);


    return res;
}

/*判断左右字节点是否都相等*/
public boolean HasNode(TreeNode root1, TreeNode root2){

    //如果Tree2已经遍历完了都能对应的上，返回true
    if (root2 == null)
        return true;

    //Tree1遍历完了，Tree2却没遍历完，返回false
    if (root1 == null)
        return false;

    //Tree1和Tree2子节点不等，返回false
    if (root1.val != root2.val)
        return false;

    //以上条件都满足，递归向下去匹配左右孩子
    return HasNode(root1.left,root2.left) && HasNode(root1.right,root2.right);
}