网站布局方法分类重庆seowhy整站优化

题目

考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

一、代码实现

func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {// 递归法遍历叶子节点（网页3、5）var getLeaves func(root *TreeNode) []intgetLeaves = func(root *TreeNode) []int {if root == nil {return []int{}}if root.Left == nil && root.Right == nil {return []int{root.Val}}// 左子树优先遍历保证顺序（网页2、3）return append(getLeaves(root.Left), getLeaves(root.Right)...)}leaves1 := getLeaves(root1)leaves2 := getLeaves(root2)return reflect.DeepEqual(leaves1, leaves2)
}

二、算法分析

1. 核心思路

• 深度优先遍历：递归遍历二叉树，优先访问左子树，确保叶子节点按从左到右顺序收集
• 序列比对：比较两棵树的叶子值序列是否完全一致

2. 关键步骤

1. 递归终止条件：空节点返回空数组，叶子节点返回自身值
2. 递归分解：将左右子树的叶子序列合并
3. 最终比对：使用reflect.DeepEqual判断切片相等性

3. 复杂度

指标	值	说明
时间复杂度	O(n)	每个节点访问一次，n为节点总数
空间复杂度	O(h)	h为树的高度（递归栈空间）

三、图解示例

以二叉树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]为例：

四、边界条件与扩展

1. 特殊场景验证

• 空树对比：root1=nil, root2=nil → true
• 结构不同但叶序相同：如root1=[1,2,3], root2=[1,3,2] → false
• 单节点树：root1=[5], root2=[5] → true

2. 多语言实现

# Python实现（网页2、3）
class Solution:def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:def dfs(node):if not node: return []if not node.left and not node.right: return [node.val]return dfs(node.left) + dfs(node.right)return dfs(root1) == dfs(root2)

// Java实现（网页4）
class Solution {public boolean leafSimilar(TreeNode root1, TreeNode root2) {List<Integer> list1 = new ArrayList<>();List<Integer> list2 = new ArrayList<>();dfs(root1, list1);dfs(root2, list2);return list1.equals(list2);}private void dfs(TreeNode node, List<Integer> list) {if (node == null) return;if (node.left == null && node.right == null) list.add(node.val);dfs(node.left, list);dfs(node.right, list);}
}

五、总结与扩展

1. 核心创新点

• 递归分治策略：将复杂问题分解为子树处理
• 顺序保障机制：左子树优先遍历确保叶序一致性
• 内存优化设计：Go语言切片操作避免全局变量

2. 扩展应用

• 并行遍历优化：使用协程同时遍历两棵树，实时比对叶子值
• 非递归实现：用栈模拟递归过程，避免栈溢出风险
• 流式处理：边遍历边比较，提前终止不匹配的情况

3. 工程优化方向

• 内存预分配：根据树高度预切片容量（Go语言）
• 迭代器模式：实现叶子节点迭代器支持大规模数据处理
• 并发安全：添加互斥锁支持多线程环境下的遍历