【LeetCode每日一题】——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,2,3], root2 = [1,3,2]
  输出：false

六【题目提示】

• 给定的两棵树结点数在 [1, 200] 范围内
• 给定的两棵树上的值在 [0, 200] 范围内

七【解题思路】

• 使用先序遍历两棵树，判断叶子节点分别加入到各自的数组
• 如果数组个数不一样返回false
• 然后遍历数组如果有不一样的返回false
• 到最后如果都没返回false就返回true

八【时间频度】

• 时间复杂度：$O(n+m)$，其中$n、m$为树的结点个数
• 空间复杂度：$O(Lo{g}_{2}N+Lo{g}_{2}M)$，其中$N、M$为树的结点个数

九【代码实现】

1. Java语言版

package Tree;

import java.util.ArrayList;
import java.util.List;

public class p872_TreesWithSimilarLeaves {
    

    int val;
    p872_TreesWithSimilarLeaves left;
    p872_TreesWithSimilarLeaves right;

    public p872_TreesWithSimilarLeaves() {
    
    }

    public p872_TreesWithSimilarLeaves(int val, p872_TreesWithSimilarLeaves left, p872_TreesWithSimilarLeaves right) {
    
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public p872_TreesWithSimilarLeaves(int val) {
    
        this.val = val;
    }

    public static void main(String[] args) {
    
        p872_TreesWithSimilarLeaves root1 = new p872_TreesWithSimilarLeaves(1);
        p872_TreesWithSimilarLeaves root1left = new p872_TreesWithSimilarLeaves(2);
        p872_TreesWithSimilarLeaves root1right = new p872_TreesWithSimilarLeaves(3);
        p872_TreesWithSimilarLeaves root2 = new p872_TreesWithSimilarLeaves(1);
        p872_TreesWithSimilarLeaves root2left = new p872_TreesWithSimilarLeaves(3);
        p872_TreesWithSimilarLeaves root2right = new p872_TreesWithSimilarLeaves(2);
        root1.left = root1left;
        root1.right = root1right;
        root2.left = root2left;
        root2.right = root2right;
        boolean res = leafSimilar(root1, root2);
        System.out.println("res = " + res);
    }

    public static boolean leafSimilar(p872_TreesWithSimilarLeaves root1, p872_TreesWithSimilarLeaves root2) {
    
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        preOrder(root1, list1);
        preOrder(root2, list2);
        if (list1.size() != list2.size()) {
    
            return false;
        }
        for (int i = 0; i < list1.size(); i++) {
    
            if (list1.get(i) != list2.get(i)) {
    
                return false;
            }
        }
        return true;
    }

    public static void preOrder(p872_TreesWithSimilarLeaves root, List<Integer> nums) {
    
        if (root == null) {
    
            return;
        }
        if (root.left == null && root.right == null) {
    
            nums.add(root.val);
        }
        preOrder(root.left, nums);
        preOrder(root.right, nums);
    }

}

2. C语言版

#include<stdio.h>
#include<stdbool.h>

/*树节点结构体*/
struct TreeNode
{
    
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

void preOrder(struct TreeNode* root, int* nums, int* count)
{
    
	if (root == NULL)
	{
    
		return NULL;
	}
	if (root->left == NULL && root->right == NULL)
	{
    
		nums[*count] = root->val;
		*count = *count + 1;
	}
	preOrder(root->left, nums, count);
	preOrder(root->right, nums, count);
}

bool leafSimilar(struct TreeNode* root1, struct TreeNode* root2)
{
    
	int nums1[201];
	int nums2[201];
	int count1 = 0;
	int count2 = 0;
	preOrder(root1, nums1, &count1);
	preOrder(root2, nums2, &count2);
	if (count1 != count2)
	{
    
		return false;
	}
	for (int i = 0; i < count1; i++)
	{
    
		if (nums1[i] != nums2[i])
		{
    
			return false;
		}
	}
	return true;
}

/*主函数省略*/

十【提交结果】

1. Java语言版
   

2. C语言版