题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。

我们规定空树不是任何树的子结构。

样例

树A：

     8
    / \
   8   7
  / \
 9   2
    / \
   4   7

树B：

   8
  / \
 9   2

返回 true ,因为B是A的子结构。

算法

(二叉树，递归) $O(nm)$

代码分为两个部分：

1. 遍历树A中的所有非空节点R；
2. 判断树A中以R为根节点的子树是不是包含和树B一样的结构，且我们从根节点开始匹配；

对于第一部分，我们直接递归遍历树A即可，遇到非空节点后，就进行第二部分的判断。

对于第二部分，我们同时从根节点开始遍历两棵子树：

• 如果树B中的节点为空，则表示当前分支是匹配的，返回true；
• 如果树A中的节点为空，但树B中的节点不为空，则说明不匹配，返回false；
• 如果两个节点都不为空，但数值不同，则说明不匹配，返回false；
• 否则说明当前这个点是匹配的，然后递归判断左子树和右子树是否分别匹配即可；

时间复杂度

最坏情况下，我们对于树A中的每个节点都要递归判断一遍，每次判断在最坏情况下需要遍历完树B中的所有节点。
所以时间复杂度是 $O(nm)$，其中 $n$ 是树A中的节点数， $m$ 是树B中的节点数。

参考文献

yxc大神的题解

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(pRoot1==NULL||pRoot2==NULL)return false;
        if(isSame(pRoot1,pRoot2))return true;
        return hasSubtree(pRoot1->left,pRoot2)||hasSubtree(pRoot1->right,pRoot2);
    }
    bool isSame(TreeNode*pRoot1,TreeNode*pRoot2){
        if(pRoot2==NULL)return true;
        if(pRoot1==NULL||pRoot1->val!=pRoot2->val)return false;
        return isSame(pRoot1->left,pRoot2->left)&&isSame(pRoot1->right,pRoot2->right);
    }
};

C 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSame(struct TreeNode*pRoot1,struct TreeNode*pRoot2){
    if(pRoot2==NULL)return true;
    if(pRoot1==NULL||pRoot1->val!=pRoot2->val)return false;
    return isSame(pRoot1->left,pRoot2->left)&&isSame(pRoot1->right,pRoot2->right);
}
bool hasSubtree(struct TreeNode* pRoot1, struct TreeNode* pRoot2) {
    if(pRoot1==NULL||pRoot2==NULL)return false;
    if(isSame(pRoot1,pRoot2))return true;
    return hasSubtree(pRoot1->left,pRoot2)||hasSubtree(pRoot1->right,pRoot2);
}

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasSubtree(TreeNode pRoot1, TreeNode pRoot2) {
        if(pRoot1==null||pRoot2==null)return false;
        if(isSame(pRoot1,pRoot2))return true;
        return hasSubtree(pRoot1.left,pRoot2)||hasSubtree(pRoot1.right,pRoot2);
    }
    public boolean isSame(TreeNode pRoot1,TreeNode pRoot2){
        if(pRoot2==null)return true;
        if(pRoot1==null||pRoot1.val!=pRoot2.val)return false;
        return isSame(pRoot1.left,pRoot2.left)&&isSame(pRoot1.right,pRoot2.right);
    }
}

Python 代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def hasSubtree(self, pRoot1, pRoot2):
        """
        :type pRoot1: TreeNode
        :type pRoot2: TreeNode
        :rtype: bool
        """
        if pRoot1==None or pRoot2==None:
            return False
        if self.isSame(pRoot1,pRoot2):
            return True
        return self.hasSubtree(pRoot1.left,pRoot2)or self.hasSubtree(pRoot1.right,pRoot2)
    def isSame(self,pRoot1,pRoot2):
        if pRoot2==None:
            return True
        if pRoot1==None or pRoot1.val!=pRoot2.val:
            return False
        return self.isSame(pRoot1.left,pRoot2.left)and self.isSame(pRoot1.right,pRoot2.right)

Javascript 代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} pRoot1
 * @param {TreeNode} pRoot2
 * @return {boolean}
 */
var isSame=function(pRoot1,pRoot2){
    if(pRoot2==null)return true;
    if(pRoot1==null||pRoot1.val!=pRoot2.val)return false;
    return isSame(pRoot1.left,pRoot2.left)&&isSame(pRoot1.right,pRoot2.right);
};
var hasSubtree = function(pRoot1, pRoot2) {
    if(pRoot1==null||pRoot2==null)return false;
    if(isSame(pRoot1,pRoot2))return true;
    return hasSubtree(pRoot1.left,pRoot2)||hasSubtree(pRoot1.right,pRoot2);
};

Python3 代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def hasSubtree(self, pRoot1, pRoot2):
        """
        :type pRoot1: TreeNode
        :type pRoot2: TreeNode
        :rtype: bool
        """
        if pRoot1==None or pRoot2==None:
            return False
        if self.isSame(pRoot1,pRoot2):
            return True
        return self.hasSubtree(pRoot1.left,pRoot2)or self.hasSubtree(pRoot1.right,pRoot2)
    def isSame(self,pRoot1,pRoot2):
        if pRoot2==None:
            return True
        if pRoot1==None or pRoot1.val!=pRoot2.val:
            return False
        return self.isSame(pRoot1.left,pRoot2.left)and self.isSame(pRoot1.right,pRoot2.right)

Go 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSame(pRoot1*TreeNode,pRoot2*TreeNode)bool{
    if pRoot2==nil{
        return true
    }
    if pRoot1==nil||pRoot1.Val!=pRoot2.Val{
        return false
    }
    return isSame(pRoot1.Left,pRoot2.Left)&&isSame(pRoot1.Right,pRoot2.Right)
}
func hasSubtree(pRoot1 *TreeNode, pRoot2 *TreeNode) bool {
    if pRoot1==nil||pRoot2==nil{
        return false
    }
    if isSame(pRoot1,pRoot2){
        return true
    }
    return hasSubtree(pRoot1.Left,pRoot2)||hasSubtree(pRoot1.Right,pRoot2)
}