872. Leaf-Similar Trees

📘 題目敘述（依 LeetCode 官網翻譯）

給定兩棵二元樹，分別由根節點 root1 與 root2 表示。

一棵二元樹的 葉節點序列（leaf value sequence） 定義如下：

由左到右列出該樹中所有的葉節點值。

如果兩棵樹的葉節點序列完全相同，請回傳 true；

否則回傳 false。

條件限制（依 LeetCode 官網）

每棵樹的節點數介於 1 到 200 之間
0 <= Node.val <= 200

🧠 解題思路

我的做法是把這題拆成兩個明確的步驟：

分別對 root1 和 root2 做 DFS
- 只在遇到「葉節點」時，才把節點值存進對應的 vector
最後比較兩棵樹得到的「葉節點序列」是否完全一致

因為 DFS 本身就是「先左後右」，

所以葉節點被收集進 vector 的順序，自然就是題目要求的「由左到右」。

所有變數

類別成員

v1：儲存 root1 的葉節點序列
v2：儲存 root2 的葉節點序列

函式相關

find(TreeNode* root, int n)
- root：目前 DFS 走到的節點
- n：
  - 1 → 表示正在處理第一棵樹，結果存進 v1
  - 2 → 表示正在處理第二棵樹，結果存進 v2
r1、r2：暫存葉節點的數值後再 push 進 vector
i：最後比較兩個葉節點序列時使用的索引

🪜 主要流程步驟

1️⃣ DFS 收集葉節點（`find` 函式）

情況一：`root == nullptr`

代表走到空節點
直接結束遞迴，避免錯誤

情況二：目前節點是葉節點

判斷條件：

root->left == nullptr && root->right == nullptr

處理方式：

若 n == 1 → 將 root->val 存入 v1
若 n == 2 → 將 root->val 存入 v2

情況三：目前節點不是葉節點

繼續遞迴左子樹
再遞迴右子樹

這樣可以確保葉節點的收集順序是「由左到右」。

2️⃣ 收集兩棵樹的葉節點序列

find(root1, 1) → 收集第一棵樹的葉節點到 v1
find(root2, 2) → 收集第二棵樹的葉節點到 v2

3️⃣ 比較兩個葉節點序列

步驟一：比長度

若 v1.size() != v2.size() → 葉節點數量不同，直接回傳 false

步驟二：逐一比值

從左到右逐一比較
只要有任一位置的值不同 → 回傳 false

若全部相同，回傳 true。

💻 程式碼實作

/**
 * Definition for a binary tree node.
 * 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:
    vector<int> v1;
    vector<int> v2;

    void find(TreeNode* root, int n) {
        if (root == nullptr) {
            return;
        }
        if (root->left == nullptr && root->right == nullptr) {
            if (n == 1) {
                v1.push_back(root->val);
            } else {
                v2.push_back(root->val);
            }
        } else {
            find(root->left, n);
            find(root->right, n);
        }
    }

    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        find(root1, 1);
        find(root2, 2);

        if (v1.size() != v2.size()) {
            return false;
        }
        for (int i = 0; i < v1.size(); i++) {
            if (v1[i] != v2[i]) {
                return false;
            }
        }
        return true;
    }
};

🔗 題目連結

https://leetcode.com/problems/leaf-similar-trees/