经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
LeetCode.872-叶子值相等的树(Leaf-Similar Trees)
来源:cnblogs  作者:小川94  时间:2019/5/15 10:27:17  对本文有异议

这是悦乐书的第334次更新,第358篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第204题(顺位题号是872)。考虑二叉树的所有叶子,从左到右的顺序,这些叶子的值形成叶子值序列。

例如,在上面给定的树中,叶子值序列是(6,7,4,9,8)。

如果两个二叉树的叶子值序列相同,则认为两个二叉树是叶子相似的。当且仅当具有头节点root1和root2的两个给定树是叶类似的时,才返回true。

注意

  • 两个给定的树将具有1到100个节点。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

题目的意思是给定两个二叉树,如果它们的叶子值都相等,就返回true。

也就是说,我们需要拿到二叉树的所有叶子节点的值,然后依次比较,如果相等就返回true。
从树的结构上来看,使用广度遍历的方式更好,整体思路就是使用广度优先算法,得到叶子节点值数组,再比较数组值判断是否相等。

此解法是借助栈,通过迭代的方式来实现广度优先算法。

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. class Solution {
  11. public boolean leafSimilar(TreeNode root1, TreeNode root2) {
  12. List<Integer> list = getLeafValue(root1);
  13. List<Integer> list2 = getLeafValue(root2);
  14. if (list.size() != list2.size()) {
  15. return false;
  16. }
  17. for (int i=0; i<list.size(); i++) {
  18. if (list.get(i) != list2.get(i)) {
  19. return false;
  20. }
  21. }
  22. return true;
  23. }
  24. public List getLeafValue(TreeNode root){
  25. List<Integer> list = new ArrayList<Integer>();
  26. Stack<TreeNode> stack = new Stack<TreeNode>();
  27. stack.push(root);
  28. while (!stack.isEmpty()) {
  29. int size = stack.size();
  30. for (int i=0; i<size; i++) {
  31. TreeNode node = stack.pop();
  32. if (node.left != null) {
  33. stack.push(node.left);
  34. }
  35. if (node.right != null) {
  36. stack.push(node.right);
  37. }
  38. if (node.left == null && node.right == null) {
  39. list.add(node.val);
  40. }
  41. }
  42. }
  43. return list;
  44. }
  45. }


03 第二种解法

针对广度优先算法,我们也可以使用递归的方式来实现。
递归方法中使用了两个参数,一是二叉树本身,二是存储叶子节点值的数组。

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. class Solution {
  11. public boolean leafSimilar(TreeNode root1, TreeNode root2) {
  12. List<Integer> list = new ArrayList<Integer>();
  13. List<Integer> list2 = new ArrayList<Integer>();
  14. getLeafValue(root1, list);
  15. getLeafValue(root2, list2);
  16. if (list.size() != list2.size()) {
  17. return false;
  18. }
  19. for (int i=0; i<list.size(); i++) {
  20. if (list.get(i) != list2.get(i)) {
  21. return false;
  22. }
  23. }
  24. return true;
  25. }
  26. public void getLeafValue(TreeNode root, List<Integer> list){
  27. if (root != null) {
  28. if (root.left == null && root.right == null) {
  29. list.add(root.val);
  30. }
  31. getLeafValue(root.left, list);
  32. getLeafValue(root.right, list);
  33. }
  34. }
  35. }


04 第三种解法

在第二种解法的基础上,我们可以将数组换成字符串,思路和效果都是一样的。

  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. class Solution {
  11. public boolean leafSimilar(TreeNode root1, TreeNode root2) {
  12. StringBuilder sb = new StringBuilder();
  13. StringBuilder sb2 = new StringBuilder();
  14. getLeafValue(root1, sb);
  15. getLeafValue(root2, sb2);
  16. return sb.toString().equals(sb2.toString());
  17. }
  18. public void getLeafValue(TreeNode root, StringBuilder sb){
  19. if (root != null) {
  20. if (root.left == null && root.right == null) {
  21. sb.append(root.val);
  22. }
  23. getLeafValue(root.left, sb);
  24. getLeafValue(root.right, sb);
  25. }
  26. }
  27. }


05 小结

算法专题目前已连续日更超过六个月,算法题文章204+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

原文链接:http://www.cnblogs.com/xiaochuan94/p/10867352.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号