当前位置 博文首页 > 数据结构和算法：LeetCode 872. 叶子相似的树
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
如果想要保证顺序，我们可以使用DFS，具体统计可以看下视频
视频链接
叶子节点统计出来了，我们只需要判断统计结果的是否完全一致即可，来看下代码。
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
//记录root1的的叶子节点
List<Integer> mListLeaf1 = new ArrayList<>();
//记录root2的的叶子节点
List<Integer> mListLeaf2 = new ArrayList<>();
dfs(root1, mListLeaf1);
dfs(root2, mListLeaf2);
//下面是判断统计两棵树的叶子节点值是否一样
if (mListLeaf1.size() != mListLeaf2.size())
return false;
for (int i = 0; i < mListLeaf1.size(); i++) {
if (mListLeaf1.get(i) != mListLeaf2.get(i))
return false;
}
return true;
}
//统计树的叶子节点
private void dfs(TreeNode root, List<Integer> mList) {
//边界条件判断，如果是空，直接返回
if (root == null)
return;
//如果是叶子节点，就把叶子节点的值加入到集合mList中
if (root.left == null && root.right == null) {
mList.add(root.val);
//叶子节点是没有子节点的，不需要再往下找了
return;
}
//如果不是叶子节点，分别统计当前节点左右子树的叶子节点
dfs(root.left, mList);
dfs(root.right, mList);
}
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
//sb1和sb2分别记录root1和root2的叶子节点的值
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
dfs(root1, sb1);
dfs(root2, sb2);
return sb1.toString().equals(sb2.toString());
}
private void dfs(TreeNode root, StringBuilder sb) {
//边界条件判断，如果是空，直接返回
if (root == null)
return;
//如果是叶子节点，就把叶子节点的值加入到StringBuilder中
if (root.left == null && root.right == null) {
sb.append(root.val + "#");
return;
}
//如果不是叶子节点，分别统计当前节点左右子树的叶子节点
dfs(root.left, sb);
dfs(root.right, sb);
}
