题目:输入两颗二叉树A和B,判断B是不是A的子结构.
核心代码:
func hasSubTree(root:TreeNode?,subRoot:TreeNode?) -> Bool {
var result:Bool = false
if root != nil && subRoot != nil {
if root!.data! == subRoot!.data! {
result = isExistSubTree(root: root, subRoot: subRoot)
}
if !result {
result = hasSubTree(root: root?.leftChild, subRoot: subRoot)
}
if !result {
result = hasSubTree(root: root?.rightChild, subRoot: subRoot)
}
}
return result
}
func isExistSubTree(root:TreeNode?,subRoot:TreeNode?) -> Bool {
if subRoot == nil {
return true
}
if root == nil {
return false
}
if root!.data! != subRoot!.data! {
return false
}
return isExistSubTree(root: root?.leftChild, subRoot: subRoot?.leftChild) && isExistSubTree(root: root?.rightChild, subRoot: subRoot?.rightChild)
}
测试代码:
var node1 = TreeNode(data: "4",leftChild: nil,rightChild: nil)
var node2 = TreeNode(data: "7",leftChild: nil,rightChild: nil)
var node3 = TreeNode(data: "2",leftChild: node1,rightChild: node2)
var node4 = TreeNode(data: "9",leftChild: nil,rightChild: nil)
var node5 = TreeNode(data: "8",leftChild: node4,rightChild: node3)
var node6 = TreeNode(data: "7",leftChild: nil,rightChild: nil)
var rootNode = TreeNode(data: "8",leftChild: node5,rightChild: node6)
var cnode1 = TreeNode(data: "9",leftChild: nil,rightChild: nil)
var cnode2 = TreeNode(data: "2",leftChild: nil,rightChild: nil)
var subRootNode = TreeNode(data: "8",leftChild: cnode1,rightChild: cnode2)
var searchTree:SearchTree = SearchTree()
var result:Bool = searchTree.hasSubTree(root: rootNode, subRoot: subRootNode)
if result {
print("FlyElephat-包含子🌲")
} else {
print("FlyElephat-不包含子🌲")
}