547,叶子相似的树
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}
截止到目前我已经写了500多道算法题了,为了方便大家阅读,我把部分算法题整理成了pdf文档,目前有1000多页,大家可以在公众号中回复关键字“pdf”即可获取下载链接。