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