。

#xff08;我们约定空树不是任意一个树的子结构#xff09;

假如给定A为{8,8,7,9,2,#,#,#,#,4,7}#xff0c;B为{8,9,2}#xff0c;2个树的结构如下#xff…题目

来源JZ26

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

我们约定空树不是任意一个树的子结构

假如给定A为{8,8,7,9,2,#,#,#,#,4,7}B为{8,9,2}2个树的结构如下可以看出B是A的子结构

数据范围:

{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}

返回值

官方题解讲得一塌糊涂关键概念没解释就算了代码逻辑还非常混乱。

这题的难度应该算较难而不是中等因为有个关键点很难想到。

假设两棵树分别为A,BB为子树则B为A的子树有如下三种情况

显然这三种情况都需要递归但因为第一种情况和后两种是有本质区别的所以第一种情况就需要单独写一个函数来判断假设为IsSubtree。

由于题目规定空树不是任意树的子树所以HasSubtree开头就要排除B为空的情况则这会引入一个关键点IsSubtree中传入的B树的节点如果为空则当前的IsSubtree的递归层数至少是两层该B树节点不可能在第一层而且前几层一定都是匹配成功的所以一定要返回true。

下面举例说明

显然当递归层中的B树节点为空时前几层的节点是匹配成功的所以要返回true。

图中总共要处理两次B树节点为空的情况两次都要返回trueB树才能正确匹配A树。

这点确实是比较难的这点想不到这题就不可能做对。

3.此时A树节点和B树节点都不空判断它们的值是否相等若不相等则返回false。

4.此时A树节点和B树节点都不空且相等则递归判断它们的左右子树是否也都相等。

bool

}这个函数是本题的核心写对了后面就很简单了假设主函数为HasSubtree则算法如下

1.判断B树或A树的节点是否空空则返回false题目规定空树不是任意树的子树。

2.调用IsSubtree判断B和A的根节点是否相同且B是否为A的子树如果是则返回true。

3.此时B和A的根节点不同递归判断B是否为A的左右子树的子树。

完整代码如下