【leetcode】872. 叶子相似的树（leaf-similar-trees）（dfs）[简单]

链接

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

耗时

解题：57 min
题解：3 min

题意

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

提示：

• 给定的两棵树可能会有 1 到 200 个结点。
• 给定的两棵树上的值介于 0 到 200 之间。

思路

对于两棵树，深搜整棵树，按顺序记录下所有叶子节点，然后比较两棵树的叶子节点序列是否一致。

时间复杂度： O ( t r e e 1 _ n o d e _ n u m + t r e e 2 _ n o d e _ n u m ) O(tree1\_node\_num+tree2\_node\_num) O(tree1_node_num+tree2_node_num)

AC代码

/**
 * 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 {
private:
    
public:
    void dfs(TreeNode* root, vector<int>& leaf_seq) {
        if(root == NULL) return ;
        
        if(root->left == NULL && root->right == NULL) {
            leaf_seq.push_back(root->val);
            return ;
        }
        
        dfs(root->left, leaf_seq);
        dfs(root->right, leaf_seq);
    }
    
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> leaf_seq_1, leaf_seq_2;
        dfs(root1, leaf_seq_1);
        dfs(root2, leaf_seq_2);
        return leaf_seq_1 == leaf_seq_2;
    }
};