树的子结构

转载：https://blog.csdn.net/qinian_ztc/article/details/104731375

看到某博主写的博客，逻辑很清晰，记录学习一下

参考网上的博客得出的子树和子结构的区别:子树的意思是包含了一个结点，就得包含这个结点下的所有节点，一棵大小为n的二叉树有n个子树，就是分别以每个结点为根的子树。子结构的意思是包含了一个结点，可以只取左子树或者右子树，或者都不取。

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

思路：

• 1.在大树中找到与小树根节点相同的节点；

• 2.大树以此为根节点，向下搜索并对比是否与小树节点相同，相同返回true，否则为false；

• 3.如果第二步返回false回到第一步，从大树的左子树查找与小树根节点相同的节点；

• 4.如果第三步最终返回false回到第一步，从大树的右子树查找与小树根节点相同的节点。

  public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    // 第一步
    if(root2 == null || root1 == null) return false;
    boolean result = false;
    if(root1.val == root2.val){
        // 第二步
        result = hasSubtreeHelper(root1, root2);
    }
    //第三步
    if(!result) result = HasSubtree(root1.left, root2);
    //第四步
    if(!result) result = HasSubtree(root1.right, root2);
    return result;
  }
  
  private boolean hasSubtreeHelper(TreeNode root1,TreeNode root2){
  
    if(root2 == null) return true;
    if(root1 == null) return false;
    if(root1.val != root2.val) return false;
    return hasSubtreeHelper(root1.left, root2.left)&& hasSubtreeHelper(root1.right, root2.right);
  }