音频网站开发,在线做qq空间的网站,装潢设计培训班学费多少钱,黄江做网站题目
来源#xff1a;JZ26 树的子结构 描述 输入两棵二叉树A#xff0c;B#xff0c;判断B是不是A的子结构。#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的子结构
数据范围: 0 A的节点个数 10000 0 B的节点个数 10000 示例1 输入 {8,8,7,9,2,#,#,#,#,4,7},{8,9,2} 返回值 true 示例2 输入 {1,2,3,4,5},{2,4} 返回值 true 示例3 输入 {1,2,3},{3,1} 返回值 false
解析
官方题解讲得一塌糊涂关键概念没解释就算了代码逻辑还非常混乱。这题的难度应该算较难而不是中等因为有个关键点很难想到。假设两棵树分别为A,BB为子树则B为A的子树有如下三种情况 1.B和A的根节点相同B为A的子树。 2.B和A的根节点不同B为A的左子树的子树。 3.B和A的根节点不同B为A的右子树的子树。 显然这三种情况都需要递归但因为第一种情况和后两种是有本质区别的所以第一种情况就需要单独写一个函数来判断假设为IsSubtree。由于题目规定空树不是任意树的子树所以HasSubtree开头就要排除B为空的情况则这会引入一个关键点IsSubtree中传入的B树的节点如果为空则当前的IsSubtree的递归层数至少是两层该B树节点不可能在第一层而且前几层一定都是匹配成功的所以一定要返回true。 下面举例说明
显然当递归层中的B树节点为空时前几层的节点是匹配成功的所以要返回true。图中总共要处理两次B树节点为空的情况两次都要返回trueB树才能正确匹配A树。这点确实是比较难的这点想不到这题就不可能做对。 关键点解决了IsSubtree的算法就不难写了 1.判断B树节点是否空若空则返回true。 2.判断A树节点是否为空若空则返回false。 3.此时A树节点和B树节点都不空判断它们的值是否相等若不相等则返回false。 4.此时A树节点和B树节点都不空且相等则递归判断它们的左右子树是否也都相等。 IsSubtree的实现如下
bool IsSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (!pRoot2 ) return true;if (!pRoot1 || pRoot1-val ! pRoot2-val)return false;return IsSubtree(pRoot1-left, pRoot2-left) IsSubtree(pRoot1-right, pRoot2-right);
}这个函数是本题的核心写对了后面就很简单了假设主函数为HasSubtree则算法如下 1.判断B树或A树的节点是否空空则返回false题目规定空树不是任意树的子树。 2.调用IsSubtree判断B和A的根节点是否相同且B是否为A的子树如果是则返回true。 3.此时B和A的根节点不同递归判断B是否为A的左右子树的子树。 完整代码如下
bool IsSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (!pRoot2 ) return true;if (!pRoot1 || pRoot1-val ! pRoot2-val)return false;return IsSubtree(pRoot1-left, pRoot2-left) IsSubtree(pRoot1-right, pRoot2-right);
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (!pRoot1 || !pRoot2)return false;return IsSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1-left, pRoot2)|| HasSubtree(pRoot1-right, pRoot2) ;
}
