二叉树的子结构

前言

牛客网剑指offer的66道题，刷起来！每道题会提供简单的思路以及测试通过的代码

题目描述

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

二叉树结构：

 class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

注：点击左下角的阅读原文即可跳转到原文，可以提交代码

解答思路

对于与二叉树有关的题目，90% 是采取递归的方式来解决比较简单的，这道题也是。

首先我们先以 A 的根节点 root1 作为起点来判断 B 是否为 A的子结构。 如果是则直接返回 true，如果不是，则递归以 root1.left 和 root1.right 作为起点来判断。代码如下：

public class 树的子结构 {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root2 == null || root1 == null) {
            return false;
        }
        // 判断 B 是否为 A 的子结构
        return isSubTree(root1, root2);
    }

    // 判断 B 是否为 A 的子结构
  private boolean isSubTree(TreeNode root1, TreeNode root2) {
      if (root1 == null) {
          return false;
      }// 以root1为root2的根节点，判断子结构是否成立
      if (judge(root1, root2)) {
          return true;
      } else {
          // 如果root1作为起点不行，则递归判断左右节点
          return isSubTree(root1.left, root2) || isSubTree(root1.right, root2);
      }
    }
    // 以root1为root2的根节点，判断子结构是否成立
    private boolean judge(TreeNode root1, TreeNode root2) {
        if(root2 == null)
            return true;
        if(root1 == null)
            return false;
        if(root1.val == root2.val)
            return judge(root1.left, root2.left) && judge(root1.right, root2.right);

        return false;
    }
}

收藏

喜欢 0