剑指Offer26.树的子结构

题目

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构, 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

3
/ 4   5
/ 1   2
给定的树 B:

4
/
1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1:

输入:A = [1,2,3], B = [3,1]
输出:false
示例 2:

输入:A = [3,4,5,1,2], B = [4,1]
输出:true
限制:

0 <= 节点个数 <= 10000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

递归

首先先序遍历A树,找到B树的根节点
找到B树的根节点以后进一步校验B是否和A的一个子树拥有相同的结构和节点值
主函数:
    如果两棵树都为空,返回true
    如果其中一颗树为空,返回false
    如果当前A树节点为B树根节点,进入校验函数
    如果当前A树节点不是B树根# 题目

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构, 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

3
/ 4   5
/ 1   2
给定的树 B:

4
/
1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1:

输入:A = [1,2,3], B = [3,1]
输出:false
示例 2:

输入:A = [3,4,5,1,2], B = [4,1]
输出:true
限制:

0 <= 节点个数 <= 10000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

递归

首先先序遍历A树,找到B树的根节点
找到B树的根节点以后进一步校验B是否和A的一个子树拥有相同的结构和节点值
主函数:
    如果两棵树都为空,返回true
    如果其中一颗树为空,返回false
    如果当前A树节点为B树根节点,进入校验函数
    如果当前A树节点不是B树根节点,递归进入A树左子树查找
    如果A树左子树也没找到,递归进入A树右子树查找
校验函数:
    如果B树节点为空,表示B树已经遍历完,返回true
    如果B树不为空,A树已经为空了,返回false
    如果两树节点值不同,返回false
    如果两树节点值相同,递归继续效验左右子树

时间复杂度 O(MN): 其中 M,N 分别为树 A 和 树 B 的节点数量
空间复杂度 O(M) : 当树 A 和树 B 都退化为链表时,递归调用深度最大。节点,递归进入A树左子树查找
    如果A树左子树也没找到,递归进入A树右子树查找
校验函数:
    如果B树节点为空,表示B树已经遍历完,返回true
    如果B树不为空,A树已经为空了,返回false
    如果两树节点值不同,返回false
    如果两树节点值相同,递归继续效验左右子树

时间复杂度 O(MN): 其中 M,N 分别为树 A 和 树 B 的节点数量
空间复杂度 O(M) : 当树 A 和树 B 都退化为链表时,递归调用深度最大。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubStructure(A *TreeNode, B *TreeNode) bool {
	if A == nil && B == nil{
		return true
	}
	// 空二叉树不属于任何树子树
	if A == nil || B == nil{
		return false
	}
	//var ret bool
	//if A.Val == B.Val{
	//	ret = helper(A,B)
	//}
	//if !ret{
	//	ret = isSubStructure(A.Left,B)
	//}
	//if !ret{
	//	ret = isSubStructure(A.Right,B)
	//}
	//return ret
	// 判断两二叉树根节点是否相等,如果相等则继续递归左右判断是否包含整个子树
	// 如果不相等,递归左子树
	// 如果A左子树也没有包含B树的,递归右子树
	return helper(A,B) || isSubStructure(A.Left,B) || isSubStructure(A.Right,B)
}

func helper(a *TreeNode,b *TreeNode) bool {
	// b树为空,说明遍历完了,A中包含子树B
	if b == nil{
		return true
	}
	// a树为空,说明A树遍历完了,但B树还有,所以A树不包含子树B
	if a == nil{
		return false
	}
	// a树和b树节点不相等
	if a.Val != b.Val{
		return false
	}
	// 如果相等,继续递归左右子树判断剩余部分是否符合
	return helper(a.Left,b.Left) && helper(a.Right,b.Right)
}

剑指Offer26.树的子结构

上一篇:CF1559D1. Mocha and Diana (Easy Version)


下一篇:lua_State数据结构