领扣LintCode算法问题答案-1495. 叶子相似的树

领扣LintCode算法问题答案-1495. 叶子相似的树

1495. 叶子相似的树

描述

请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个叶值序列 。

举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是叶相似的。

如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

• 给定的两颗树可能会有 1 到 100 个结点。

样例 1：

输入: {1,#,2,3}, {1,2,#,3}
输出: true
解释: 
第一棵树：1\                2                /                 3   
第二棵树：1/2/
3
叶值序列都为：[3]，所以相同

样例 2：

输入: {1,#,2,3}, {1,2,3}
输出: false
解释: 
第一棵树：1\                2                /                 3   
第二棵树：1/ \                2   3    
第一棵树叶值序列都：[3]，第二个树为：[2, 3]，所以不相同

题解

/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* }*/public class Solution {
    /*** @param root1: the first tree* @param root2: the second tree* @return: returns whether the leaf sequence is the same*/public boolean leafSimilar(TreeNode root1, TreeNode root2) {
    // write your code here.List<Integer> seq1 = this.getLeafSeq(root1);List<Integer> seq2 = this.getLeafSeq(root2);return seq1.equals(seq2);}private List<Integer> getLeafSeq(TreeNode root) {
    List<Integer> seq = new ArrayList<>();Stack<TreeNode> s = new Stack<TreeNode>();s.push(root);while (!s.isEmpty()) {
    TreeNode n = s.pop();if (n.left == null&& n.right == null) {
    seq.add(n.val);} else {
    if (n.left != null) {
    s.push(n.left);}if (n.right != null) {
    s.push(n.right);}}}return seq;}
}

原题链接点这里

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。
欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。