剑指offer2之树的结构

题目(树的子结构)

输入两棵二叉树 A 和 B ，判断 B 是不是 A 的子结构。二叉树的定义如下：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
        val(x), left(nullptr), right(nullptr) {
    }
};  

算法思路

首先应注意所输入二叉树的特殊值情况，如空指针。
算法主要分为两步。
第一步，首先应该从二叉树 A 的根节点开始遍历，寻找和二叉树 B 根节点相同的那个节点，设为 节点 C。我们对二叉树 A 遍历的时候可以利用二叉树的递归特性,对其左右子树执行相同操作。
第二步，需要判断树 A 中以 C 为根节点的子树的结构是否和树 B 的结构一样，那么仍然可以利用递归的特性。如果他们的根节点值相同，那么对树 A 中 C 的左子树和树 B 中 C 的左子树递归判断结构的一致性，然后对两棵树的 C 的右子树也递归，只有他们的子结构同时相同，那么二叉树 A 中才存在 二叉树 B 的结构，否则不存在。

算法实现

复杂度分析

二叉树 A 利用层序遍历的递归实现，每个结点只需遍历一次，故时间复杂度为 O(n)。而使用了递归，最差情况下递归调用的深度为 O(n)，所以空间复杂度为 O(n)。本题中还需要遍历二叉树 B，因此若设其节点数为 m 个，那么最终的时间复杂度为 O(n+m)，空间复杂度为 O(n+m)。

参考

<<剑指offer2>>