题目
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
例:
输入:root = [3,4,5,1,2], subRoot = [4,1,2]
输出:true
方法:递归
整体思路为在第一棵二叉树 root 中寻找与第二棵二叉树 subRoot 的根节点的值相同的结点,然后以此节点为基础进行判断是否包含,若不包含则继续寻找下一个相同的,直至遍历完第一棵二叉树或确定包含
- 主要部分:首先要判断第一棵二叉树(或其子树)和第二棵二叉树是否为空,若其中之一为空,即两个树不同。然后判断两棵树(子树)根节点的值是否相等,若相等并且第一棵树(子树)在结构和数值上均与第二棵树相同,那么表示存在;若不相等,则需要继续递归,寻找合适的节点
- 比较部分:同 100. 相同的树
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isSubtree(self, root, subRoot):
if root == None and subRoot == None:
return True
elif root == None or subRoot == None:
return False
if root.val == subRoot.val and self.compare(root, subRoot) == True:
return True
else:
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
def compare(self, p, q):
if p == None and q != None:
return False
elif p != None and q == None:
return False
elif p == None and q == None:
return True
elif p.val != q.val:
return False
left = self.compare(p.left, q.left)
right = self.compare(p.right, q.right)
return left and right
网友评论