本文共 1569 字，大约阅读时间需要 5 分钟。
为了判断两棵树是否为“叶子相似的树”，我们需要确保两棵树的叶子节点在同样的顺序下具有相同的值。以下是解决问题的详细步骤：
理解问题：叶子相似树要求两棵树的叶子节点顺序一致且对应相等。例如，树一的叶子依次为A、B、C，树二的叶子同样为A、B、C。
选择算法：使用深度优先搜索（DFS）来遍历每棵树的叶子节点。对于每个节点，判断其是否为叶子节点（左右子节点均为空），如果是，则记录其值。收集完成后，比较两棵树的叶子值列表。
递归函数设计：设计一个递归函数遍历树，收集叶子节点的值。该函数首先检查当前节点是否为叶子节点，若是则记录值，否则分别递归处理左右子树。
优化思考：避免不必要的递归，确保叶子节点的顺序一致性。通过先处理左子树再处理右子树的顺序，确保叶子值的收集顺序与树的结构有关。
// 定义TreeNode结构体struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}};class Solution {public: void dfs(TreeNode* root, vector & res) { if (!root->left && !root->right) { res.push_back(root->val); return; } else { // 先处理左子树 if (root->left) { dfs(root->left, res); } // 再处理右子树 if (root->right) { dfs(root->right, res); } } } bool leafSimilar(TreeNode* root1, TreeNode* root2) { vector res1, res2; // 处理根1 if (root1) { dfs(root1, res1); } // 处理根2 if (root2) { dfs(root2, res2); } // 比较结果 return res1 == res2; }}; TreeNode结构体：定义了二叉树的节点，包含值、左指针和右指针。
dfs函数：使用递归遍历树，收集叶子节点的值。当节点左右都为空时，表示为叶子，直接将值添加到结果列表中。
处理左右子树：分别处理左子树和右子树，确保按照预定顺序（先左后右）收集叶子节点的值。
leafSimilar函数：比较两棵树的叶子值列表，返回两个列表是否相等，判断两棵树是否为叶子相似树。
这种方法确保了两种树的叶子节点顺序和值的完全一致性，解决了问题。
转载地址：http://vpfvz.baihongyu.com/