题解 | #树的子结构#

描述

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

基本思路

按照树 A 中每个节点的遍历顺序比较当前节点和 B 的根节点是否相同，如果相同就按照 B 的结构遍历他们的每个节点。
例子是题目所给的样例：

 A : {8,8,#,9,#,2,#,5}
 B : {8,9,#,2}

1.两个节点都是 8 ，根节点相同，开始遍历其他节点。

2. 第二个节点不相同函数结束

3. 继续比较 A 中节点和 B 的根节点，再次发现相同

4. 按照 B 的顺序遍历所有节点发现 B 是 A 的子树

复杂度分析

在最坏情况下， 把 A 遍历了一遍，并且对于每个根节点都把 B 遍历了一遍，假设 A 和 B 分别有 m, n 个节点， 所以最坏的时间复杂度是 O（m * n）。

算法实现

详尽的注释都写在 c++ 版本的代码中。

1. 递归方式

   // c++
   class Solution {
   public:
    // 函数返回子树 p1 和 p2 是否有相同结构
    bool isSub(TreeNode* p1, TreeNode* p2) {
        if (!p2) return true;
        else if (!p1) return false;
   
        // p1 和 p2 的根节点相同并且 p1 和 p2 的左子树和右子树分别相同
        return p1->val == p2->val && isSub(p1->left, p2->left) && isSub(p1->right, p2->right);
    }
   
    // 函数返回树 p1 中是否有子树 p2
    bool HasSubtree(TreeNode* p1, TreeNode* p2) {
        if (!p1 || !p2) return false;
   
        // p1 和 p2 结构相同，或者 p1 左子树或者右子树中有 p2
        return isSub(p1, p2) || HasSubtree(p1->left, p2) || HasSubtree(p1->right, p2);
    }
   };

   # python3
   class Solution:
    def isSub(self, p1, p2):
        if not p2: return True 
        if not p1: return False
        return p1.val == p2.val and self.isSub(p1.left, p2.left) and self.isSub(p1.right, p2.right)
    def HasSubtree(self, p1, p2):
        if not p1 or not p2: return False
        return self.isSub(p1, p2) or self.HasSubtree(p1.left, p2) or self.HasSubtree(p1.right, p2)

2. 非递归方式

   // c++
   class Solution {
   public:
    bool isSub(TreeNode* p1, TreeNode* p2) {
        if (!p2) return true;
        if (!p1) return false;
        return p1->val == p2->val && isSub(p1->left, p2->left) && isSub(p1->right, p2->right);
    }
   
    // 中序遍历的方式遍历树 p1
    bool HasSubtree(TreeNode* p1, TreeNode* p2) {
        if (!p2) return false;
        stack<TreeNode*> st;
        while (p1 || !st.empty()) {
            while (p1) {
                if (p1->val == p2->val && isSub(p1, p2)) return true;
                st.push(p1);
                p1 = p1->left;
            }
            TreeNode* t = st.top();
            st.pop();
            p1 = t->right;
        }
        return false;
    }