【Day14】872.叶子相似的树

872. 叶子相似的树

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

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

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

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

示例 1:

输入:root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出:true

示例 2:

输入:root1 = [1], root2 = [1]
输出:true

示例 3:

输入:root1 = [1], root2 = [2]
输出:false

示例 4:

输入:root1 = [1,2], root2 = [2,2]
输出:true

示例 5:

输入:root1 = [1,2,3], root2 = [1,3,2]
输出:false

提示:

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

题解:

将第一次的结果存储下来后,后面直接比较并返回结果。

class Solution {
public:
    int index = 0;
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector r1;
        dfs1(root1, r1);
        return dfs2(root2, r1) && index == r1.size();
    }
    void dfs1(TreeNode* root, vector& res) {
        if (!root) return;
        if (!root->left && !root->right) {
            res.push_back(root->val);
            return;
        }
        dfs1(root->left, res);
        dfs1(root->right, res);
    }
    bool dfs2(TreeNode* root, vector& res) {
        if (!root) return true;
        if (!root->left && !root->right) {
            if (index >= res.size()) return false;
            if (root->val != res[index]) return false;
            index++;
            return true;
        }
        return dfs2(root->left, res) && dfs2(root->right, res);
    }

};

   转载规则


《【Day14】872.叶子相似的树》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day15】1734.解码异或后的排列 【Day15】1734.解码异或后的排列
1734. 解码异或后的排列给你一个整数数组 perm ,它是前 n 个正整数的排列,且 n 是个 奇数 。 它被加密成另一个长度为 n - 1 的整数数组 encoded ,满足 encoded[i] = perm[i] XOR perm
2021-05-11
下一篇 
【Day13】1482.制作m束花所需的最少天数 【Day13】1482.制作m束花所需的最少天数
1482. 制作 m 束花所需的最少天数给你一个整数数组 bloomDay,以及两个整数 m 和 k 。 现需要制作 m 束花。制作花束时,需要使用花园中 相邻的 k 朵花 。 花园中有 n 朵花,第 i 朵花会在 bloomDay[i]
2021-05-09
  目录