原创

【剑指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肯定不具有相同的结点;如果它们的值相同,则递归地判断它们各自的左右节点的值是不是相同。递归的终止条件是我们到达了树A或者树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
正文到此结束
本文目录