题解 | #相逆叶子#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的是二叉树的遍历和叶子节点的提取，同时需要进行逆序的比较操作。

题目解答方法的文字分析

我们使用深度优先搜索（DFS）来遍历两棵树并提取叶子节点，然后对比这两个叶子序列是否逆序相等。

具体步骤如下：

1. 实现一个递归的深度优先搜索函数 dfs，用于遍历树并提取叶子节点。
2. 在深度优先搜索函数中，对于每个节点，如果其左右子节点都为空，则说明是叶子节点，将其值添加到叶子序列中。
3. 分别对两棵树调用深度优先搜索函数，得到两个叶子序列 leaves1 和 leaves2。
4. 反序 leaves2，将其元素顺序逆转。
5. 比较 leaves1 和逆序后的 leaves2 是否相等，如果相等则返回 true，否则返回 false。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> leaves1, leaves2;
        dfs(root1, leaves1); // 提取第一棵树的叶子序列
        dfs(root2, leaves2); // 提取第二棵树的叶子序列
        
        // 将 leaves2 反序
        reverse(leaves2.begin(), leaves2.end());
        
        // 比较两个叶子序列是否相等
        return leaves1 == leaves2;
    }
    
    void dfs(TreeNode* node, vector<int>& leaves) {
        if (!node) {
            return;
        }
        if (!node->left && !node->right) {
            leaves.push_back(node->val);
            return;
        }
        dfs(node->left, leaves);
        dfs(node->right, leaves);
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！