872. Leaf-Similar Trees

[songyy5517]

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence. 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.

Example 1:

Input: 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]
Output: true

Example 2:

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

Intuition The problem is to compare whether the value and sequence of the leaf nodes of two binary trees are the same. A simple idea is to travarse two trees with DFS, and extract all their leaf nodes into a container, and finally compare whether the elements in two containers are equal.

[songyy5517]

Approach: DFS

1. Exception handling;
2. Define two arraylists to store the leaf nodes of two binay tree;
3. Iterate over the two trees with DFS, and put their leaf nodes into the two arraylists respectively;
4. Compare whether the elements in the two arraylists are the same.

Complexity Analysis

• Time complexity: $O(N + M)$ , $N$ and $M$ are the number of nodes of two trees respectively, and travarsing all the nodes of two trees takes $O(N+M)$ time;
• Space complexity: $O(N+M)$ , additionally define two arraylists to store their leaf nodes, taking up $O(N+M)$ space.

[songyy5517]

/**
 * 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 {
    ArrayList<Integer> a1 = new ArrayList();
    ArrayList<Integer> a2 = new ArrayList();

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        // Intuitioin: Collect all leaf nodes through DFS, and then compare. 
        // 1. Exception handling
        if (root1 == null || root2 == null)
            return false;

        dfs(root1, a1);
        dfs(root2, a2);

        return a1.equals(a2);
    }

    void dfs(TreeNode root, ArrayList<Integer> a){
        if (root == null)
            return ;

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

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

[songyy5517]

2024/5/30