【LeetCode】叶子相似的树 Java 题解

HQ数字卡

关注

发布于: 2021 年 05 月 10 日

题目描述

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

举个例子，如上图所示，给定一棵叶值序列为 (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
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/leaf-similar-trees著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这是一个简单题目，分析之后，需要两个函数，一个函数是获取树所有叶子节点，一个函数是判断叶子节点是否相同。
获取所有叶子节点的时候，可以采用 dfs 的方式获取。dfs 有递归和非递归两种方式，都可以实现。

AC 代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public boolean leafSimilar(TreeNode root1, TreeNode root2) {        List<Integer> leftList1 = new ArrayList<>();        List<Integer> leftList2 = new ArrayList<>();        getTreeLeaf(root1, leftList1);        getTreeLeaf(root2, leftList2);
        return leafListSimilar(leftList1, leftList2);    }
    public void getTreeLeaf(TreeNode root, List<Integer> leftList) {        if (root == null) {            return;        }        if (root.left == null && root.right == null) {            leftList.add(root.val);            return;        }        if (root.left != null) {            getTreeLeaf(root.left, leftList);        }        if (root.right != null) {            getTreeLeaf(root.right, leftList);        }    }
    public boolean leafListSimilar(List<Integer> leftList1, List<Integer> leftList2) {        int n1 = leftList1.size();        int n2 = leftList2.size();
        if (n1 != n2) {            return false;        }
        for (int i = 0; i < n1 ; i++) {            if (leftList1.get(i) != leftList2.get(i)) {                return false;            }        }        return true;    }}

复制代码

总结

上述代码的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持每日一题，加油！

发布于: 2021 年 05 月 10 日阅读数: 8

原文链接:【http://xie.infoq.cn/article/66759d55e2e14edb00f40f4de】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】叶子相似的树 Java 题解

题目描述

思路分析

AC 代码

总结

HQ数字卡

评论