JZ-017-树的子结构
树的子结构 题目描述
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)代码
【JZ-017-树的子结构】题目链接: 树的子结构
/**
* 标题:树的子结构
* 题目描述
* 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
* 题目链接:
* https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&&tqId=11170&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
*/
public class Jz17 {public static void main(String[] args) {
TreeNode root1 = new TreeNode(2);
TreeNode root2 = new TreeNode(2);
Jz17 jz17 = new Jz17();
System.out.println(jz17.hasSubtree(root1, root2));
}public boolean hasSubtree(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) {
return false;
}return isSubtreeWithRoot(root1, root2) || hasSubtree(root1.left, root2) || hasSubtree(root1.right, root2);
}/**
* 递归法
*
* @param root1
* @param root2
* @return
*/
private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {
if (root2 == null) {
return true;
}
if (root1 == null) {
return false;
}
if (root1.val != root2.val) {
return false;
}
return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);
}
}
【每日寄语】 总之岁月漫长,然而值得等待。
推荐阅读
- 热闹中的孤独
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 放屁有这三个特征的,请注意啦!这说明你的身体毒素太多
- 一个人的旅行,三亚
- 布丽吉特,人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事,我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量