547，叶子相似的树

Original 博哥数据结构和算法 2022-05-11

收录于合集 #算法图文分析 161个

Gentle attitude for a heart to be contempt indeed is a great comfort.

柔和的态度对于一颗被轻蔑的心是很大的安慰。

问题描述

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

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

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

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

示例 1：

输入：
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]
输出：true

示例 2：

输入：root1 = [1], root2 = [1]
输出：true

示例 3：

输入：root1 = [1], root2 = [2]
输出：false

示例 4：

输入：root1 = [1,2], root2 = [2,2]
输出：true

示例5：

输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false

提示：

给定的两棵树可能会有1到200个结点。
给定的两棵树上的值介于0到200之间。

dfs解决

这题是让判断两棵树的叶子节点从左往右的排列顺序是否一样，一种常见的方式就是先统计每棵树叶子节点的值。统计树的叶子节点比较简单，只需要遍历每一个节点，判断是否是叶子节点，如果是叶子节点就把它的值加入到list集合中。最后在判断这两棵树的叶子节点集合是否完全相同即可。

遍历树的每一个节点会有多种方式，我们首先来看一下BFS是否可以，BFS是一层层的遍历的，如下图所示，遍历的结果是[6，9，8，7，4]，很明显是错误的，因为顺序弄乱了。

如果想要保证顺序，我们可以使用DFS，具体统计可以看下视频

叶子节点统计出来了，我们只需要判断统计结果的是否完全一致即可，来看下代码。

 1public boolean leafSimilar(TreeNode root1, TreeNode root2) {
 2    //记录root1的的叶子节点
 3    List<Integer> mListLeaf1 = new ArrayList<>();
 4    //记录root2的的叶子节点
 5    List<Integer> mListLeaf2 = new ArrayList<>();
 6    dfs(root1, mListLeaf1);
 7    dfs(root2, mListLeaf2);
 8    //下面是判断统计两棵树的叶子节点值是否一样
 9    if (mListLeaf1.size() != mListLeaf2.size())
10        return false;
11    for (int i = 0; i < mListLeaf1.size(); i++) {
12        if (mListLeaf1.get(i) != mListLeaf2.get(i))
13            return false;
14    }
15    return true;
16}
17
18//统计树的叶子节点
19private void dfs(TreeNode root, List<Integer> mList) {
20    //边界条件判断，如果是空，直接返回
21    if (root == null)
22        return;
23    //如果是叶子节点，就把叶子节点的值加入到集合mList中
24    if (root.left == null && root.right == null) {
25        mList.add(root.val);
26        //叶子节点是没有子节点的，不需要再往下找了
27        return;
28    }
29    //如果不是叶子节点，分别统计当前节点左右子树的叶子节点
30    dfs(root.left, mList);
31    dfs(root.right, mList);
32}

StringBuilder解决

除了上面使用集合List，我们还可以使用StringBuilder，原理都是一样的，换汤不换药，来看下代码。

 1public boolean leafSimilar(TreeNode root1, TreeNode root2) {
 2    //sb1和sb2分别记录root1和root2的叶子节点的值
 3    StringBuilder sb1 = new StringBuilder();
 4    StringBuilder sb2 = new StringBuilder();
 5    dfs(root1, sb1);
 6    dfs(root2, sb2);
 7    return sb1.toString().equals(sb2.toString());
 8}
 9
10private void dfs(TreeNode root, StringBuilder sb) {
11    //边界条件判断，如果是空，直接返回
12    if (root == null)
13        return;
14    //如果是叶子节点，就把叶子节点的值加入到StringBuilder中
15    if (root.left == null && root.right == null) {
16        sb.append(root.val + "#");
17        return;
18    }
19    //如果不是叶子节点，分别统计当前节点左右子树的叶子节点
20    dfs(root.left, sb);
21    dfs(root.right, sb);
22}