[每日 LeetCode] 872. Leaf-Similar Trees

原文链接 [每日 LeetCode] 872. Leaf-Similar Trees

Description:

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.

思路：本题题意是要求判断两棵树的叶子结点是否相同，包括位置和值。一开始想复杂了，在考虑怎么从左到右记录下每棵树的叶子结点。后来发现不用，直接对两个树遍历即可，每次遍历到叶子结点就记录下来，如果两棵树的叶子结点相同，遍历的结果应该也是相同的。另外，提交运行时间又一个 0ms❤️ 。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> op1, op2;
        dfs(root1, op1);
        dfs(root2, op2);
        return op1 == op2;
    }
    
    void dfs(TreeNode* root, vector<int>& v)
    {
        if(root == nullptr)    return;
        if(root->left == nullptr && root->right == nullptr)
            v.push_back(root->val);    
        dfs(root->left, v);
        dfs(root->right, v);
    }
};
​

运行时间：0ms

运行内存：14.2M