树的子结构

题目

牛客网

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

解题思路

  1. 遍历查找相等根节点
  2. 通过递归查找当前根节点下是否包含子树 root2
  1. public boolean HasSubtree(TreeNode root1, TreeNode root2) {
  2.     if (root2 == null) {
  3.         return false;
  4.     }
  6.     LinkedList<TreeNode> pipeline = new LinkedList<>();
  7.     pipeline.addLast(root1);
  9.     while (!pipeline.isEmpty()) {
  10.         TreeNode node = pipeline.pop();
  11.         if (node == null) {
  12.             continue;
  13.         }
  15.         pipeline.addLast(node.left);
  16.         pipeline.addLast(node.right);
  18.         if (node.val == root2.val && isSub(node, root2)) {
  19.             return true;
  20.         }
  21.     }
  23.     return false;
  24. }
  26. private boolean isSub(TreeNode root1, TreeNode root2) {
  27.     if (root1 == null && root2 == null) {
  28.         return true;
  29.     }
  31.     if (root1 == null) {
  32.         return false;
  33.     }
  35.     if (root2 == null) {
  36.         return true;
  37.     }
  39.     if (root1.val == root2.val) {
  40.         return isSub(root1.left, root2.left) && isSub(root1.right, root2.right);
  41.     } else {
  42.         return false;
  43.     }
  45. }