"原文链接 [每日 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 le .."

[每日 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

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    127 引用 • 35 回帖
  • Tree
    19 引用 • 5 回帖
  • Easy
    79 引用 • 10 回帖
感谢    关注    收藏    赞同    反对    举报    分享
回帖    
请输入回帖内容...