剑指26：树的子结构

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

/*
    1.先序遍历树 A 中的每个节点 node_A
    	实现函数 HasSubtree(A, B)
    2.判断树 A 中 以 node_A 为根节点的子树是否包含树 B
    	实现函数 isSame(A, B)

    时间复杂度：O(nm)
        其中 n 是树A中的节点数，m 是树B中的节点数。
        最坏情况下，树A中的每个节点都需要递归判断一遍，每次递归在最坏情况下需要遍历树B中的所有节点。
    空间复杂度：O(n)
        当树 A 和树 B 都退化为链表时，递归调用深度最大。
*/
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		if (pRoot1 == nullptr || pRoot2 == nullptr) return false;

		return isSame(pRoot1, pRoot2)
			|| HasSubtree(pRoot1->left, pRoot2)
			|| HasSubtree(pRoot1->right, pRoot2);
    }

	bool isSame(TreeNode* node1, TreeNode* node2) {
		if (node2 == nullptr) return true;
		if (node1 == nullptr || node1->val != node2->val) return false;
		return isSame(node1->left, node2->left)
			&& isSame(node1->right, node2->right);
	}
};

C++ 代码 - leetcode

/*
    1.先序遍历树 A 中的每个节点 node_A
    2.判断树 A 中 以 node_A 为根节点的子树是否包含树 B

    时间复杂度：O(nm)
    空间复杂度：O(n)
*/
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (!A || !B) return false;

        return isSame(A, B)
            || isSubStructure(A->left, B)
            || isSubStructure(A->right, B);
    }

    bool isSame(TreeNode* A, TreeNode* B) {
        if (!B) return true;
        if (!A || A->val != B->val) return false;

        return isSame(A->left, B->left)
            && isSame(A->right, B->right);
    }
};