领扣LintCode算法问题答案-1495. 叶子相似的树
目录
1495. 叶子相似的树描述样例 1：样例 2：
题解鸣谢
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]，所以不相同
题解
public class Solution {
public boolean leafSimilar(TreeNode root1
, TreeNode root2
) {
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
;
}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。
