Easy

题目描述

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

例如，在上面给定的树中，叶子值序列是 (6, 7, 4, 9, 8)。

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

当且仅当两个给定的树具有头节点 root1 和 root2 的树是叶子相似的时，返回 true。

示例 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 遍历获取叶子序列：分别对两棵树进行深度优先搜索，按照从左到右的顺序收集所有叶子节点的值
  2. 比较序列：将两个叶子值序列进行比较

解法分析：

  • 方法一：先收集再比较 - 分别遍历两棵树收集叶子节点到数组中，然后比较数组是否相等
  • 方法二：同步遍历比较 - 使用迭代器或生成器同步遍历两棵树，边遍历边比较，一旦发现不同就立即返回

推荐方法一，代码更清晰易懂。对于节点数不超过200的题目约束，空间开销可以接受。

实现要点：

  • 判断叶子节点：当前节点的左右子树都为空
  • DFS遍历顺序：先遍历左子树，再遍历右子树，确保叶子节点按从左到右的顺序被收集
  • 最后比较两个叶子序列的长度和每个位置的值是否都相等

代码实现

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> leaves1, leaves2;
        getLeaves(root1, leaves1);
        getLeaves(root2, leaves2);
        return leaves1 == leaves2;
    }
    
private:
    void getLeaves(TreeNode* root, vector<int>& leaves) {
        if (!root) return;
        
        if (!root->left && !root->right) {
            leaves.push_back(root->val);
            return;
        }
        
        getLeaves(root->left, leaves);
        getLeaves(root->right, leaves);
    }
};

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def getLeaves(root):
            if not root:
                return []
            
            if not root.left and not root.right:
                return [root.val]
            
            return getLeaves(root.left) + getLeaves(root.right)
        
        return getLeaves(root1) == getLeaves(root2)

public class Solution {
    public bool LeafSimilar(TreeNode root1, TreeNode root2) {
        var leaves1 = new List<int>();
        var leaves2 = new List<int>();
        
        GetLeaves(root1, leaves1);
        GetLeaves(root2, leaves2);
        
        if (leaves1.Count != leaves2.Count) return false;
        
        for (int i = 0; i < leaves1.Count; i++) {
            if (leaves1[i] != leaves2[i]) return false;
        }
        
        return true;
    }
    
    private void GetLeaves(TreeNode root, List<int> leaves) {
        if (root == null) return;
        
        if (root.left == null && root.right == null) {
            leaves.Add(root.val);
            return;
        }
        
        GetLeaves(root.left, leaves);
        GetLeaves(root.right, leaves);
    }
}

var leafSimilar = function(root1, root2) {
    const getLeaves = (root) => {
        if (!root) return [];
        
        if (!root.left && !root.right) {
            return [root.val];
        }
        
        return [...getLeaves(root.left), ...getLeaves(root.right)];
    };
    
    const leaves1 = getLeaves(root1);
    const leaves2 = getLeaves(root2);
    
    if (leaves1.length !== leaves2.length) return false;
    
    for (let i = 0; i < leaves1.length; i++) {
        if (leaves1[i] !== leaves2[i]) return false;
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m + n)m 和 n 分别为两棵树的节点数，需要遍历所有节点
空间复杂度O(h + l)h 为树的高度（递归栈空间），l 为叶子节点数量（存储叶子序列）