题目:

输入两棵二叉树A 和B，判断B 是不是A 的子结构。

思路：

要查找树A 中是否存在和树B 结构一样的子树，我们可以分成两步： 第一步在树A 中找到和B 的根结点的值一样的结点R， 第二步再判断树A 中以R 为根结点的子树是不是包含和树B 一样的结构。

代码:

树节点:

#import <Foundation/Foundation.h>
// 树节点
@interface NSBinaryTreeNode : NSObject
// 值
@property (nonatomic, strong) NSString *value;
// 左节点
@property (nonatomic, strong) NSBinaryTreeNode *left;
// 右节点
@property (nonatomic, strong) NSBinaryTreeNode *right;
@end

#import "NSBinaryTreeNode.h"
#import <Foundation/Foundation.h>


/**
 判断 子树 是不是 根树的子结构。

 @param rootTreeHeaderNode 根树
 @param subTreeHeaderNode 子树
 @return 返回 是否 一直
 */
BOOL matchBinaryTree (NSBinaryTreeNode *rootTreeHeaderNode, NSBinaryTreeNode *subTreeHeaderNode) {
    if ([rootTreeHeaderNode isEqual:subTreeHeaderNode]) {
        return NO;
    }
    
    // 当 子树节点为空， 返回一致
    if (subTreeHeaderNode == nil) {
        return YES;
    }
    
     // 子树的根结点不为空，如果根树的根结点为空就返回false
    if (rootTreeHeaderNode == nil) {
        return NO;
    }
    
     // 如果两个结点的值相等，则分别判断其左子结点和右子结点
     if ([rootTreeHeaderNode.value isEqualToString:subTreeHeaderNode.value]) {
          return matchBinaryTree(rootTreeHeaderNode.left, subTreeHeaderNode.left) && matchBinaryTree(rootTreeHeaderNode.right, subTreeHeaderNode.right);
     }
 
    return NO;
}


/**
 根数rootTreeHeaderNode 是否 包含 子树 subTreeHeaderNode

 @param rootTreeHeaderNode 根数
 @param subTreeHeaderNode 子树
 @return 是否包含
 */
BOOL containerSubBinaryTree (NSBinaryTreeNode *rootTreeHeaderNode, NSBinaryTreeNode *subTreeHeaderNode) {
    
    if (rootTreeHeaderNode == nil) {
        return NO;
    }
    
    if (subTreeHeaderNode == nil) {
        return NO;
    }
    
    if ([rootTreeHeaderNode.value isEqualToString:subTreeHeaderNode.value]) {
        BOOL isContainer = matchBinaryTree(rootTreeHeaderNode, subTreeHeaderNode);
        if (isContainer) {
            return YES;
        }
    }

    return containerSubBinaryTree(rootTreeHeaderNode.left, subTreeHeaderNode) || containerSubBinaryTree(rootTreeHeaderNode.right, subTreeHeaderNode);
}


int main(int argc, const char * argv[]) {
    @autoreleasepool {

        NSBinaryTreeNode *root = [NSBinaryTreeNode new];
        root.value = @"8";
        root.left = [NSBinaryTreeNode new];
        root.left.value = @"6";
        root.left.left = [NSBinaryTreeNode new];
        root.left.left.value = @"5";
        root.left.right = [NSBinaryTreeNode new];
        root.left.right.value = @"7";
        root.right = [NSBinaryTreeNode new];
        root.right.value = @"10";
        root.right.left = [NSBinaryTreeNode new];
        root.right.left.value = @"9";
        root.right.right = [NSBinaryTreeNode new];
        root.right.right.value = @"11";
        
        NSBinaryTreeNode *subRoot = [NSBinaryTreeNode new];
        subRoot.value = @"8";
        subRoot.left = [NSBinaryTreeNode new];
        subRoot.left.value = @"6";
        subRoot.right = nil;
        subRoot.left.left = [NSBinaryTreeNode new];
        subRoot.left.left.value = @"5";
        subRoot.right.right = nil;
        
        BOOL isContainer = containerSubBinaryTree(root, subRoot);
        
        NSLog(@"---: %d", isContainer);
    }
    return 0;
}