• 树的子结构
    • 题目
    • 解题思路

    树的子结构

    题目

    牛客网

    输入两棵二叉树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. }