【剑指Offer】017——树的子结构（树）

题目描述

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

解题思路

要查找树A是否存在和树B结构一样的子树，我们可以分成两步：第一步在树A中找到和树B的根节点的值一样的节点R,第二步再判断树A中以R为根节点的子树是不是包含和树B一样的结构。

file

如上图所示：首先我们试着在树A中找到值为8(树B的根节点的值)的节点。从树A的根节点开始遍历，我们发现它的根节点就是8。接着我们就去判断树A的根节点下面的子树是不是含有和树B一样的结构。在树A中，根节点的左子节点的值是8，而树B的根节点的左子节点是9，对应的两个节点不同。

因此，我们仍需要遍历树A，接着查找值为8的节点。我们在树的第二层找到了一个值为8的节点，然后进行第二步判断，即判断这个节点下面的子树是否含有和树B一样结构的子树。于是我们遍历这个节点下面的子树，先后得到两个子节点9和2，这和B树的结构完全相同。此时我们在树A中找到了一个和树B的结构一样的子树，因此树B是树A的子结构。

​ 第一步在树A中查找与根节点一样的节点，实际上就是树的遍历，可以采用递归的方式；第二步是判断树A中以R为根节点的子树是不是和树B具有相同的结构。同样，我们也可以用递归的思路来考虑：如果节点R的值和树B的根节点不相同，则以R为根节点的子树和树B肯定不具有相同的结点；如果它们的值相同，则递归地判断它们各自的左右节点的值是不是相同。递归的终止条件是我们到达了树Ａ或者树B的叶节点。

参考代码

Java

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
       if(root2==null) return false;
       if(root1==null && root2!=null) return false;      
        boolean flag = false;
        // 根节点比较
        if(root1.val==root2.val){
            flag = isSubTree(root1,root2);
        }
        // 继续比较左、右子树
        if(!flag){
            flag = HasSubtree(root1.left, root2);
            if(!flag){
                flag = HasSubtree(root1.right, root2);
            }
        }
        return flag;
    }
    private boolean isSubTree(TreeNode root1, TreeNode root2) {
        if(root2==null) return true;   // 子树比较完
        if(root1==null && root2!=null) return false;  // 主树比较完     
        if(root1.val==root2.val){
            // 左右子树
            return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
        }else{
        return false;
        }
    }
}

Python

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        if not pRoot1 or not pRoot2 :
            return False
        # 遍历树
        flag = False
        if pRoot1.val == pRoot2.val:
            flag = self.isSubTree(pRoot1, pRoot2)
        if not flag:
            flag = self.HasSubtree(pRoot1.left, pRoot2)
            if not flag:
                flag = self.HasSubtree(pRoot1.right, pRoot2)
        return flag
       
    def isSubTree(self,pRoot1,pRoot2):
        if not pRoot2:
            return True
        if not pRoot1 and pRoot2:
            return False
        if pRoot1.val == pRoot2.val:
            return self.isSubTree(pRoot1.left, pRoot2.left) and self.isSubTree(pRoot1.right, pRoot2.right)
        else:
            return False

个人订阅号

image