872. Leaf-Similar Trees 递归真的好用

Consider all the leaves of a binary tree.  From left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Constraints:

• Both of the given trees will have between 1 and 200nodes.
• Both of the given trees will have values between 0 and 200

之前对递归运用的不甚熟悉，最近算法刷多了自然就熟悉了，尤其对于树的便利。

这个题目，简单的保留前序过程中遇到的leaf就好，然后比较leaf列表。

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> tree1;
        vector<int> tree2;
        visitTree(root1, tree1);
        visitTree(root2, tree2);
        if(tree1.size() != tree2.size())
            return false;
        if(tree1.size() == 0 and tree2.size() == 0)
            return true;
        for(int i = 0; i < tree1.size(); i++)
        {
            if(tree1[i] != tree2[i])
                return false;
        }
        return true;
    }
private:
    void visitTree(TreeNode* root, vector<int>& res)
    {
        if(root == nullptr)
            return;
        if(root->left == nullptr and root->right == nullptr)
            res.push_back(root->val);
        visitTree(root->left, res);
        visitTree(root->right, res);
    }
};