872. 叶子相似的树

🟢   🔖  树 深度优先搜索 二叉树  🔗 力扣 LeetCode

题目

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence .

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Example 1:

Input: 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]

Output: true

Example 2:

Input: root1 = [1,2,3], root2 = [1,3,2]

Output: false

Constraints:

• The number of nodes in each tree will be in the range [1, 200].
• Both of the given trees will have values in the range [0, 200].

题目大意

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

举个例子，如上图所示，给定一棵叶值序列为 (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,2,3], root2 = [1,3,2]

输出： false

提示：

• 给定的两棵树结点数在 [1, 200] 范围内
• 给定的两棵树上的值在 [0, 200] 范围内

解题思路

1. DFS 遍历：通过 dfs 函数递归遍历树，直到找到叶子节点，每当遇到一个叶子节点时，收集叶子节点的值，并将其存储在数组中。
2. 比较叶子节点列表：遍历完两棵树的所有叶子节点后，只需要比较这两个保存叶子节点值的数组是否相等。如果相等，则返回 true，否则返回 false。

复杂度分析

• 时间复杂度：O(n)，其中 n 是树的节点总数。
  • 对于每棵树，需要遍历一次树的所有节点，因此 getLeafValues 函数的时间复杂度是 O(n)。
  • 比较两棵树的叶子节点列表需要 O(k) 时间，其中 k 是叶子节点的数量，最坏情况下 k 与 n 相等。
  • 因此，总的时间复杂度是 O(n)。
• 空间复杂度：O(n)，使用了递归来遍历树，递归调用栈的空间复杂度是 O(h)，其中 h 是树的高度。在最坏情况下，树的高度可能为 n，因此递归的空间复杂度为 O(n)，返回的 result 数组也占用 O(n) 的空间。

代码

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function (root1, root2) {
	// 获取树的叶子节点值列表
	const getLeafValues = (root) => {
		let result = [];
		const dfs = (node) => {
			if (!node) return;
			// 如果是叶子节点
			if (!node.left && !node.right) {
				result.push(node.val);
			}
			dfs(node.left);
			dfs(node.right);
		};
		dfs(root);
		return result;
	};

	// 获取两棵树的叶子节点值
	const leaves1 = getLeafValues(root1);
	const leaves2 = getLeafValues(root2);

	// 比较叶子节点值是否相同
	return leaves1.toString() === leaves2.toString();
};