[LeetCode] 872. Leaf-Similar Trees
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode] 872. Leaf-Similar Trees,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2515字,纯文字阅读大概需要4分钟。
内容图文
![[LeetCode] 872. Leaf-Similar Trees](/upload/InfoBanner/zyjiaocheng/986/4865b08b5fab4e368f880e98ac63225d.jpg)
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8)
.
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true
if and only if the two given trees with head nodes root1
and root2
are leaf-similar.
Example 1:
Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8] Output: true
Example 2:
Input: root1 = [1], root2 = [1] Output: true
Example 3:
Input: root1 = [1], root2 = [2] Output: false
Example 4:
Input: root1 = [1,2], root2 = [2,2] Output: true
Example 5:
Input: root1 = [1,2,3], root2 = [1,3,2] Output: false
Constraints:
- The number of nodes in each tree will be in the range
[1, 200]
. - Both of the given trees will have values in the range
[0, 200]
.
叶子相似的树。
请考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的,则返回 true;否则返回 false 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/leaf-similar-trees
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这是一道easy题,既然比较的是叶子节点,那么我们还是利用DFS去找到每个叶子节点,加入一个list,然后比较两个list是否相同即可。
时间O(n)
空间O(h)
Java实现
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 class Solution { 17 public boolean leafSimilar(TreeNode root1, TreeNode root2) { 18 List<Integer> list1 = new ArrayList<>(); 19 List<Integer> list2 = new ArrayList<>(); 20 helper(root1, list1); 21 helper(root2, list2); 22 return list1.equals(list2); 23 } 24 25 private List<Integer> helper(TreeNode root, List<Integer> res) { 26 if (root == null) { 27 return null; 28 } 29 if (root.left == null && root.right == null) { 30 res.add(root.val); 31 } 32 helper(root.left, res); 33 helper(root.right, res); 34 return res; 35 } 36 }
内容总结
以上是互联网集市为您收集整理的[LeetCode] 872. Leaf-Similar Trees全部内容,希望文章能够帮你解决[LeetCode] 872. Leaf-Similar Trees所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。