20_100. 相同的树
2022/3/30 6:22:20
本文主要是介绍20_100. 相同的树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
*题目描述:
解题思路:
- 深度优先搜索:同时遍历这两颗树,比对节点值是否一致,然后比对其左右节点是否相同
- 广度优先搜索:也是同时遍历,使用两个队列存储入队的节点,及时返回错误情况,最后跳出循环时,一定要注意,可能两棵树本身节点数量并不相同。
代码:
深度优先搜索
//深度优先搜索: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } if (p.val != q.val) { return false; } return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } }
广度优先搜索
//广度优先搜索: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } // if (p.val != q.val) { // return false; // } Queue<TreeNode> queue1 = new LinkedList<>(); Queue<TreeNode> queue2 = new LinkedList<>(); queue1.offer(p); queue2.offer(q); while (!queue1.isEmpty() && !queue2.isEmpty()) { TreeNode tmp1 = queue1.poll(); TreeNode tmp2 = queue2.poll(); if (tmp1.val != tmp2.val) { return false; } TreeNode left1 = tmp1.left; TreeNode left2 = tmp2.left; TreeNode right2 = tmp2.right; TreeNode right1 = tmp1.right; if (left1 == null ^ left2 == null) { return false; } if (right1 == null ^ right2 == null) { return false; } if (left1 != null) { queue1.offer(left1); } if (left2 != null) { queue2.offer(left2); } if (right1 != null) { queue1.offer(right1); } if (right2 != null) { queue2.offer(right2); } } return queue1.isEmpty() && queue2.isEmpty(); } }
这篇关于20_100. 相同的树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性