26. 树的子结构
1. 描述
输入两棵二叉树A和B，判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构)
B 是 A 的子结构， 即 A 中有出现和B相同的结构和节点值。
2. 例子
示例 1:
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2:
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
3. 限制
- 0 <= 节点个数 <= 10000
4. 题解
m 是 i_tree1 中的节点数，n 是 i_tree2 中的节点数
时间复杂度: O(mn)
空间复杂度: O(m)
class Solution
{
private:
bool isTreesEqual(TreeNode *i_tree1, TreeNode *i_tree2)
{
if(!i_tree2) return true;
return (i_tree1 && i_tree1->val == i_tree2->val) && isTreesEqual(i_tree1->left, i_tree2->left) && isTreesEqual(i_tree1->right, i_tree2->right);
}
public:
// bool isSubStructure(TreeNode* A, TreeNode* B)
bool isSubStructure(TreeNode *i_tree1, TreeNode *i_tree2)
{
if(!i_tree1 || !i_tree2) return false;
return isTreesEqual(i_tree1, i_tree2)
|| isSubStructure(i_tree1->left, i_tree2)
|| isSubStructure(i_tree1->right, i_tree2)
;
}
};