剑指Offer 18 树的子结构

题目描述

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

思路

先遍历主树，找到和子结构中根节点一样的节点，然后检验左子树，检验右子树

代码

static public boolean HasSubtree(TreeNode root1,TreeNode root2) {
       boolean result = false;
       if (root1!=null&&root2!=null)     
       {
           if (root1.val==root2.val)     //根节点相同啦
           {
               result = a(root1,root2);  //检验子树去吧
           }
           if (!result)                  //没找到，主树继续遍历
           {
               result = HasSubtree(root1.left,root2);
           }
           if (!result)
           {
               result = HasSubtree(root1.right,root2);
           }
       }
       return  result;

    }

    static  public boolean a(TreeNode root1,TreeNode root2)
    {
        if (root2==null)              //子结构的全部节点都有；
            return true;
        if (root1==null)              //子结构有的，主树没有
            return  false;
        if (root1.val!=root2.val)     //节点值不一样
            return  false;
        return a(root1.left,root2)&&a(root1.right,root2); //继续检验子树；

    }

收获

1. 树的操作要比链表更难一些；一定要注意指针；
2. 递归嵌套递归；虽然不太能写的出来，但是结构简单，代码整洁；