题解 | #树的子结构#

题目的主要信息：

• 给定两棵二叉树的层次遍历序列
• 判断二叉树B是否为A树的子树
• 我们约定空树不是任意一个树的子结构

举一反三：

学习完本题的思路你可以解决如下题目：

JZ27. 二叉树的镜像

JZ28. 对称的二叉树

方法一：两层前序遍历（推荐使用）

知识点：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路：

既然是要找到A树中是否有B树这样子树，如果是有子树肯定是要遍历这个子树和B树，将两个的节点一一比较，但是这样的子树不一定就是A树根节点开始的，所以我们还要先找到子树可能出现的位置。

既然是可能的位置，那我们可以对A树的每个节点前序递归遍历，寻找是否有这样的子树，而寻找是否有子树的时候，我们就将A树与B树同步前序遍历，依次比较节点值。

//递归比较
bool flag1 = recursion(pRoot1, pRoot2);  
//递归树1的每个节点
bool flag2 = HasSubtree(pRoot1->left, pRoot2);  
bool flag3 = HasSubtree(pRoot1->right, pRoot2);

具体做法：

• step 1：因为空树不是任何树的子树，所以要先判断B树是否为空树。
• step 2：当A树为空节点，但是B树还有节点的时候，不为子树，但是A树不为空节点，B树为空节点时可以是子树。
• step 3：每次递归比较A树从当前节点开始，是否与B树完全一致，同步前序遍历。
• step 4：A树自己再前序遍历进入子节点，当作子树起点再与B树同步遍历。
• step 5：以上情况任意只要有一种即可。

图示：

Java实现代码：

public class Solution {
    private boolean recursion(TreeNode root1, TreeNode root2){
        //当一个节点存在另一个不存在时
        if(root1 == null && root2 != null)  
            return false;
        //两个都为空则返回
        if(root1 == null || root2 == null)  
            return true;
        //比较节点值
        if(root1.val != root2.val)
            return false;
        //递归比较子树
        return recursion(root1.left, root2.left) && recursion(root1.right, root2.right);
    }

    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        //空树
        if(root2 == null) 
            return false;
        //一个为空，另一个不为空
        if(root1 == null && root2 != null)
            return false;
        if(root1 == null || root2 == null)
            return true;
        //递归比较
        boolean flag1 = recursion(root1, root2);  
        //递归树1的每个节点
        boolean flag2 = HasSubtree(root1.left, root2);  
        boolean flag3 = HasSubtree(root1.right, root2);
        return flag1 || flag2 || flag3;
    }
}

C++实现代码：

class Solution {
public:
    bool recursion(TreeNode* root1, TreeNode* root2){
        //当一个节点存在另一个不存在时
        if(root1 == NULL && root2 != NULL)  
            return false;
        //两个都为空则返回
        if(root1 == NULL || root2 == NULL)  
            return true;
        //比较节点值
        if(root1->val != root2->val)
            return false;
        //递归比较子树
        return recursion(root1->left, root2->left) && recursion(root1->right, root2->right);
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        //空树
        if(pRoot2 == NULL) 
            return false;
        //一个为空，另一个不为空
        if(pRoot1 == NULL && pRoot2 != NULL)
            return false;
        if(pRoot1 == NULL || pRoot2 == NULL)
            return true;
        //递归比较
        bool flag1 = recursion(pRoot1, pRoot2);  
        //递归树1的每个节点
        bool flag2 = HasSubtree(pRoot1->left, pRoot2);  
        bool flag3 = HasSubtree(pRoot1->right, pRoot2);
        return flag1 || flag2 || flag3;
    }
};

Python实现代码：

class Solution:
    def recursion(self, root1: TreeNode, root2: TreeNode) -> bool:
        #当一个节点存在另一个不存在时
        if root1 is None and root2 is not None:  
            return False
        #两个都为空则返回
        if root1 is None or root2 is None:  
            return True
        #比较节点值+递归比较子树
        return root1.val == root2.val and self.recursion(root1.left, root2.left) and self.recursion(root1.right, root2.right)
        
    def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool:
        #空树
        if pRoot2 is None: 
            return False
        #一个为空，另一个不为空
        if pRoot1 is None and pRoot2 is not None:
            return False
        if pRoot1 is None or pRoot2 is None:
            return True
        #递归比较
        flag1 = self.recursion(pRoot1, pRoot2) 
        #递归树1的每个节点
        flag2 = self.HasSubtree(pRoot1.left, pRoot2)
        flag3 = self.HasSubtree(pRoot1.right, pRoot2)
        return flag1 or flag2 or flag3

复杂度分析：

• 时间复杂度：$O(nm)O(nm)$，$nn$和$mm$分别表示两棵树的节点数，我们要对每个A树节点进行访问，最坏情况下每次都要比较B树节点的次数
• 空间复杂度：$O(n+m)O(n+m)$，两个递归栈深度相乘(当树退化成链表时，递归栈最大）

方法二：两层层次遍历（扩展思路）

知识点：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。

思路：

根据方法一，所以这道题的思路，无非就是在A树中遍历每个节点尝试找到那个子树，然后每次以该节点出发能不能将子树与B树完全匹配。能用前序遍历解决，我们也可以用层次遍历来解决。

首先对于A树层次遍历每一个节点，遇到一个与B树根节点相同的节点，我们就开始同步层次遍历比较以这个节点为根的树中是否出现了B树的全部节点。因为我们只考虑B树的所有节点是否在A树中全部出现，那我们就以B树为基，再进行一次层次遍历，A树从那个节点开始跟随B树一致进行层次遍历就行了，比较对应的每个点是否相同，或者B树是否有超出A树没有的节点。

//以树2为基础，树1跟随就可以了
while(!q2.isEmpty()){ 
    ...
    //树1为空或者二者不相等
    if(node1 == null || node1.val != node2.val) 
        return false;
    ...//继续层次遍历
}

层次遍历我们借助队列，根节点入队，然后取值：

q1.push(root1);
q2.push(root2);
while(...){
    TreeNode* node1 = q1.front(); 
    TreeNode* node2 = q2.front();
    ...
}

然后左右节点如果有就入队，每次队列弹出一个节点，知道队列为空，这样刚好是一层一层读取数据。

//树2还有左子树
if(node2->left){ 
    //子树入队
    q1.push(node1->left); 
    q2.push(node2->left);
}
//树2还有右子树
if(node2->right){ 
    //子树入队
    q1.push(node1->right); 
    q2.push(node2->right);
}

具体做法：

• step 1：先判断空树，空树不为子结构。
• step 2：利用队列辅助，层次遍历第一棵树，每次检查遍历到的节点是否和第二棵树的根节点相同。
• step 3：若是相同，可以以该节点为子树根节点，再次借助队列辅助，同步层次遍历这个子树与第二棵树，这个时候以第二棵树为基，只要找到第二棵树的全部节点，就算找到了子结构。

Java实现代码：

import java.util.*;
public class Solution {
    //层次遍历判断两个树是否相同
    private boolean helper(TreeNode root1, TreeNode root2){ 
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();
        q1.offer(root1);
        q2.offer(root2);
        //以树2为基础，树1跟随就可以了
        while(!q2.isEmpty()){ 
            TreeNode node1 = q1.poll(); 
            TreeNode node2 = q2.poll();
            //树1为空或者二者不相等
            if(node1 == null || node1.val != node2.val) 
                return false;
            //树2还有左子树
            if(node2.left != null){ 
                //子树入队
                q1.offer(node1.left); 
                q2.offer(node2.left);
            }
            //树2还有右子树
            if(node2.right != null){ 
                //子树入队
                q1.offer(node1.right); 
                q2.offer(node2.right);
            }
        }
        return true;
    }

    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        //空树不为子结构
        if(root1 == null || root2 == null) 
            return false;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root1);
        //层次遍历树1
        while(!q.isEmpty()){ 
            TreeNode node = q.poll();
            //遇到与树2根相同的节点，以这个节点为根判断后续子树是否相同
            if(node.val == root2.val){ 
                if(helper(node, root2))
                    return true;
            }
            //左子树入队
            if(node.left != null) 
                q.offer(node.left);
            //右子树入队
            if(node.right != null) 
                q.offer(node.right);
        }
        return false;
    }
}

C++实现代码：

class Solution {
public:
    //层次遍历判断两个树是否相同
    bool helper(TreeNode* root1, TreeNode* root2){ 
        queue<TreeNode*> q1, q2;
        q1.push(root1);
        q2.push(root2);
        //以树2为基础，树1跟随就可以了
        while(!q2.empty()){ 
            TreeNode* node1 = q1.front(); 
            TreeNode* node2 = q2.front();
            q1.pop();
            q2.pop();
            //树1为空或者二者不相等
            if(node1 == NULL || node1->val != node2->val) 
                return false;
            //树2还有左子树
            if(node2->left){ 
                //子树入队
                q1.push(node1->left); 
                q2.push(node2->left);
            }
            //树2还有右子树
            if(node2->right){ 
                //子树入队
                q1.push(node1->right); 
                q2.push(node2->right);
            }
        }
        return true;
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        //空树不为子结构
        if(pRoot1 == NULL || pRoot2 == NULL) 
            return false;
        queue<TreeNode*> q;
        q.push(pRoot1);
        //层次遍历树1
        while(!q.empty()){ 
            TreeNode* node = q.front();
            q.pop();
            //遇到与树2根相同的节点，以这个节点为根判断后续子树是否相同
            if(node->val == pRoot2->val){ 
                if(helper(node, pRoot2))
                    return true;
            }
            //左子树入队
            if(node->left) 
                q.push(node->left);
            //右子树入队
            if(node->right) 
                q.push(node->right);
        }
        return false;
    }
};

Python实现代码：

import queue
class Solution:
    #层次遍历判断两个树是否相同
    def helper(self, root1: TreeNode, root2: TreeNode) -> bool:
        q1 = queue.Queue() 
        q2 = queue.Queue() 
        q1.put(root1)
        q2.put(root2)
        #以树2为基础，树1跟随就可以了
        while not q2.empty():
            node1 = q1.get()
            node2 = q2.get()
            #树1为空或者二者不相等
            if node1 is None or node1.val != node2.val:
                return False
            #树2还有左子树
            if node2.left:
                #子树入队
                q1.put(node1.left)
                q2.put(node2.left)
            #树2还有右子树
            if node2.right: 
                #子树入队
                q1.put(node1.right) 
                q2.put(node2.right)
        return True
        
    def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool:
        #空树不为子结构
        if pRoot1 is None or pRoot2 is None: 
            return False
        q = queue.Queue() 
        q.put(pRoot1)
        #层次遍历树1
        while not q.empty():
            node = q.get()
            #遇到与树2根相同的节点，以这个节点为根判断后续子树是否相同
            if node.val == pRoot2.val:
                if self.helper(node, pRoot2):
                    return True
            #左子树入队
            if node.left: 
                q.put(node.left)
            #右子树入队
            if node.right: 
                q.put(node.right)
        return False

复杂度分析：

• 时间复杂度：$O(nm)O(nm)$，$nn$和$mm$分别表示A树和B树的节点数，我们要对每个A树节点进行访问，最坏情况下每次都要比较B树节点的次数
• 空间复杂度：$O(n)O(n)$，三个队列的长度最坏都不会超过A树的节点数