树的子结构

题目描述

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构，即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:

给定的树 B：

1
2
3

   4 
  /
 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

1 2	输入：A = [1,2,3], B = [3,1] 输出：false

示例 2：

1 2	输入：A = [3,4,5,1,2], B = [4,1] 输出：true

限制：
0 <= 节点个数 <= 10000

题目链接

Leetcode

题目解答

解法一

深度优先遍历，按照深度优先的方式遍历树A，对A中的每一个节点借助辅助函数 hasSubStructure 判断从该节点出发是否含有子结构B，如果确实存在则返回true ，利用逻辑或的短路性质在传递结果的同时也能避免不必要的递归。

时间复杂度:$O(mn)$ 空间复杂度:$O(m)$

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        boolean result = hasSubStructure(A, B);
        result = result || isSubStructure(A.left, B);
        result = result || isSubStructure(A.right, B);
        return result;
    }

    public boolean hasSubStructure(TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        if (!hasSubStructure(A.left, B.left)) return false;
        if (!hasSubStructure(A.right, B.right)) return false;
        return true;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.8 MB, 在所有 Java 提交中击败了96.95%的用户

解法二

广度优先遍历，整体思想与解法一相同，但是采用了广度优先遍历的方式，需要借助队列，从理论上来说两种方式的时间空间复杂度是一致的，但是在实际运行中维护队列会带来额外的时间和空间开销，所以解法二实际运行效果不如解法一。

时间复杂度:$O(mn)$ 空间复杂度:$O(m)$

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(A);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val == B.val && hasSubStructure(node, B)) {
                return true;
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return false;
    }

    public boolean hasSubStructure(TreeNode nodeA, TreeNode nodeB) {
        Queue<TreeNode> queueA = new LinkedList<>();
        Queue<TreeNode> queueB = new LinkedList<>();
        queueA.add(nodeA);
        queueB.add(nodeB);
        while (!queueB.isEmpty()) {
            nodeA = queueA.poll();
            nodeB = queueB.poll();
            if (nodeA == null || nodeA.val != nodeB.val) {
                return false;
            }
            if (nodeB.left != null) {
                queueA.add(nodeA.left);
                queueB.add(nodeB.left);
            }
            if (nodeB.right != null) {
                queueA.add(nodeA.right);
                queueB.add(nodeB.right);
            }
        }
        return true;
    }
}

执行用时：5 ms, 在所有 Java 提交中击败了5.72%的用户
内存消耗：40.8 MB, 在所有 Java 提交中击败了5.12%的用户