树的子结构

阅读文本大概需要 2.6 分钟。

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路

首先需要判断两棵树是否为空，只要有一棵树为空，就可以直接返回 false。

然后对根节点进行判断，如果两棵树的根节点的值相同，那么继续比较根节点的左节点与右节点。把左节点和右节点分别当做判断的起点继续判断。

如何判断：1.先判断树2是否被遍历完，如果遍历完，并且所有的值都能对应上，那么可以直接返回 true。2.如果树2没有被遍历完，然后判断树1是否被遍历完，如果树1在树2之前被遍历完，那么树2不是树1的子结构，直接返回 false。3.如果根节点的值都能匹配上，那么就分别去两个树的子节点中去匹配，又是我们熟悉的递归了。

项目源码

如果你想看到《剑指offer》的所有源码，欢迎 star 我的 github project。

《剑指offer》的 github 地址：

https://github.com/liuenci/GoOffer