【5.10】LeetCode每日一题·叶子相似的树

2021年05月10日 8时34分

标签： LeetCode dfs 树形结构

## 题目描述

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

![](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/16/tree.png)

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

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

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

#### 示例1

![](https://assets.leetcode.com/uploads/2020/09/03/leaf-similar-1.jpg)

```
输入：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

![](https://assets.leetcode.com/uploads/2020/09/03/leaf-similar-2.jpg)

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

#### 提示

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

#### 来源

> 来源：力扣（LeetCode）
> 链接：[872. 叶子相似的树 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/leaf-similar-trees/)

## 解题思路

对树进行深度优先搜索（先序、中序或者后序均可），访问到叶子节点时记录叶值序列。最后比较两棵树的叶值序列是否相等即可。

## 代码

```cpp
/**
 * 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 {
public:
    void dfs(TreeNode* root, vector<int>& res){
        if(!root->left && !root->right){
            res.push_back(root->val);
            return;
        }
        if(root->left) dfs(root->left, res);
        if(root->right) dfs(root->right, res);
    }
    vector<int> getLeafSeq(TreeNode* root){
        vector<int> res;
        dfs(root, res);
        return res;
    }
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> res1 = getLeafSeq(root1), res2 = getLeafSeq(root2);
        return res1 == res2;
    }
};
```

## 用时和内存

> 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户
> 内存消耗：12.5 MB，在所有 C++提交中击败了36.66%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【5.10】LeetCode每日一题·叶子相似的树

所有评论

暂无评论

新增评论