当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.872.Leaf-Similar Trees 叶子序列相同的二叉树

LeetCode.872.Leaf-Similar Trees 叶子序列相同的二叉树

题目描述

872 Leaf-Similar Trees
https://leetcode-cn.com/problems/leaf-similar-trees/

Consider all the leaves of a binary tree.  From left to right order, the values of those leaves form a leaf value sequence.


For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
 
Note: Both of the given trees will have between 1 and 100 nodes.


解题过程

遍历二叉树,用数组记住叶节点序列,然后比较即可
时间复杂度 O(m+n),空间复杂度 O(m+n)

private static class SolutionV2020 {
    StringBuilder sb1, sb2;
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        sb1 = new StringBuilder();
        sb2 = new StringBuilder();
        preOrder(root1, sb1);
        preOrder(root2, sb2);
        return sb1.toString().equals(sb2.toString());
    }

    private void preOrder(TreeNode root, StringBuilder sb) {
        if (null == root) {
            return;
        }
        // 叶子
        if (null == root.left && null == root.right) {
            sb.append(root.val);
        }
        preOrder(root.left, sb);
        preOrder(root.right, sb);
    }
}

GitHub代码

algorithms/leetcode/leetcode/_872_LeafSimilarTrees.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_872_LeafSimilarTrees.java


上一篇 LeetCode.897.Increasing Order Search Tree BST转升序单边树

下一篇 LeetCode.783.Minimum Distance Between BST Nodes BST的最小差值

阅读
评论
236
阅读预计1分钟
创建日期 2020-02-02
修改日期 2020-02-02
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论