###### tags: `LeetCode` `Tree` `Recursion` `Easy` `Stack` `DFS`
# LeetCode #872 [Leaf-Similar Trees](https://leetcode.com/problems/leaf-similar-trees/)
### (Easy)
請考慮一棵二元樹上所有的葉子，這些葉子的值按從左到右的順序排列形成一個 葉值序列 。
舉個例子，如上圖所示，給定一棵葉值序列為 (6, 7, 4, 9, 8) 的樹。

如果有兩棵二元樹的葉值序列是相同，那麼我們就認為它們是 葉相似 的。

如果給定的兩個根結點分別為 root1 和 root2 的樹是葉相似的，則返回 true；否則返回 false 。

---
簡單做法:

以遞迴法建立兩數組儲存兩樹的葉節點(若左右子節點皆為空則該節點為葉節點), 再比較兩數組是否相等。

class Solution {
public:
    vector<int> r1,r2;
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        helper(root1,r1);
        helper(root2,r2);
        if(r1.size()!=r2.size())return false;
        for(int i=0;i<r1.size();i++){
            if(r1[i]!=r2[i])return false;
        }
        return true;
    }
    void helper(TreeNode* node, vector<int>& v){
        if(!node)return;
        else if(!node->left&&!node->right)v.push_back(node->val);
        if(node->left)helper(node->left, v);
        if(node->right)helper(node->right, v);
    }
};

---
LeetCode版:

利用DFS特性比較兩樹的葉節點順序。

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        stack<TreeNode*> s1 , s2;
        s1.push(root1); s2.push(root2);
        while (!s1.empty() && !s2.empty())
            if (dfs(s1) != dfs(s2)) return false;//比較回傳值
        return s1.empty() && s2.empty();
    }

    int dfs(stack<TreeNode*>& s) {
        while (true) {
            TreeNode* node = s.top(); s.pop();
            if (node->right) s.push(node->right);
            if (node->left) s.push(node->left);
            if (!node->left && !node->right) return node->val;//葉節點->回傳節點值
        }
    }
};