剑指offer面试题26：树的子结构（golang实现）

题目描述

输入两棵二叉树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]		//	AB为深度优先表示的完全二叉树
输出：false

示例2

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

算法分析

• 要确定B树是否为A树的子结构，要先确定B的根节点是否被包含在A树内，因此可以考虑用广度优先搜索遍历A树的每一个节点，判断当前节点curNode的值是否等于B树的根节点，若值相等，则用isAContainsB()函数判断以curNode为根节点的树是否包含B树； 若值不相等，则直接跳过，继续遍历A树的节点。
• isAContainsB()函数用递归实现，需要注意对AB判空。
• 设A的节点数为m，B的节点数为n，则总的时间复杂度为遍历A树的时间乘上isAContainsB()函数花费的时间，即O( m ∗ n m*n m∗n)。
• 因为在BFS的过程中用到了nodes数组保存树的节点，所以空间复杂度为O( n n n)。

Golang代码如下

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isAContainsB(A *TreeNode, B *TreeNode) bool {
	if B == nil {
		return true
	}
    if A == nil {
        return false
    }
	if A.Val == B.Val {
		return isAContainsB(A.Left, B.Left) && isAContainsB(A.Right, B.Right)
	}
	return false
}

func isSubStructure(A *TreeNode, B *TreeNode) bool {
	if A == nil || B == nil {
		return false
	}
	nodes := []*TreeNode{A}
	for len(nodes) > 0 {
		curNode := nodes[0]
		if curNode.Val == B.Val {
			if isAContainsB(curNode, B) {
				return true
			}
		}
		nodes = nodes[1:]
		if curNode.Left != nil {
			nodes = append(nodes, curNode.Left)
		}
		if curNode.Right != nil {
			nodes = append(nodes, curNode.Right)
		}
	}
	return false
}