首页 > itarticle > [leetcode] problem 872 – leaf-similar trees

[leetcode] problem 872 – leaf-similar trees

admin 11月 13, 2020 0

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.

Code

public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public boolean leafSimilar(TreeNode root1, TreeNode root2) {
    List<Integer> leaves1 = new ArrayList<>();
    List<Integer> leaves2 = new ArrayList<>();
    dfs(leaves1, root1);
    dfs(leaves2, root2);
    return leaves1.equals(leaves2);
}

private void dfs(List<Integer> leaves, TreeNode root) {
    if (root == null)
        return;

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

    dfs(leaves, root.left);
    dfs(leaves, root.right);
}