Leetcode 872

Hello , 我是mz

题目要求获取这些叶子的值并按从左到右的顺序排列形成一个 叶值序列

叶，即无左右节点 , 并且还有按顺序，我们可以选择用中序遍历来完成要求

public boolean leafSimilar(TreeNode root1, TreeNode root2) {
    List<Integer> list1 = new ArrayList<>();
    List<Integer> list2 = new ArrayList<>();
    inorder(root1, list1);
    inorder(root2, list2);
    return list1.equals(list2);
}

private void inorder(TreeNode root, List<Integer> list) {
    if (root != null) {
        inorder(root.left, list);

        if (root.left == null && root.right == null)
            list.add(root.val);

        inorder(root.right, list);
    }
}

空间复杂度为O（n + m) ，n , m 分别为两个ArrayList

需要遍历整个list ，因此时间复杂度为O（n + m)