872.叶子相似的树

发表于 | 分类于
字数统计: 322 | 阅读时长 ≈ 1

一、题目描述

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

binarysearchtree_improved.png

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

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

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

提示：

  • 给定的两颗树可能会有 1 到 100 个结点。

二、题解

1.递归

1.1 思路

  1. 如果root的左右子树都为空，就将此节点加入到数组中
  2. 递归调用上述过程
  3. 对比两个数组内容

1.2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define maxSize 100
void getLeaf(struct TreeNode *root, int *arr, int *returnSize)
{
    if (root == NULL)
        return NULL;
    if (root->left == NULL && root->right == NULL)
        arr[(*returnSize)++] = root->val;
    else
    {
        getLeaf(root->left, arr, returnSize);
        getLeaf(root->right, arr, returnSize);
    }
}

bool leafSimilar(struct TreeNode *root1, struct TreeNode *root2)
{
    int arr1[maxSize];
    int len1 = 0;
    int arr2[maxSize];
    int len2 = 0;
    getLeaf(root1, arr1, &len1);
    getLeaf(root2, arr2, &len2);
    if (len1 != len2)
        return false;
    for (int i = 0; i < len1; i++)
        if (arr1[i] != arr2[i])
            return false;
    return true;
}