LeetCode //C - 872. Leaf-Similar Trees

872. 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.
?

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
Explanation:

Example 2:

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

Constraints:

• The number of nodes in each tree will be in the range [1, 200].
• Both of the given trees will have values in the range [0, 200].

From: LeetCode
Link: 872. Leaf-Similar Trees

---

Solution:

Ideas：

This code defines a helper function findLeaves to perform a depth-first search on the tree and collect the leaf values into an array. The main function leafSimilar uses this helper function to collect the leaves of both trees and then compares the arrays.

If the leaf value sequences are the same, it returns true; otherwise, it returns false.

The constraints of the problem ensure that the number of nodes in each tree will not exceed 200, which justifies the fixed size of the leaves arrays. If you’re allowed to use dynamic memory allocation, you could use linked lists or dynamically allocated arrays to potentially handle trees with more than 200 nodes.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void findLeaves(struct TreeNode* root, int* leaves, int* index) {
    if (root == NULL) return;

    // If it is a leaf node, add it to the leaves array.
    if (root->left == NULL && root->right == NULL) {
        leaves[(*index)++] = root->val;
    }

    // Recursively find leaves in the left subtree.
    findLeaves(root->left, leaves, index);
    // Recursively find leaves in the right subtree.
    findLeaves(root->right, leaves, index);
}

bool leafSimilar(struct TreeNode* root1, struct TreeNode* root2) {
    int leaves1[200] = {0}, leaves2[200] = {0};
    int index1 = 0, index2 = 0;

    // Find leaves for both trees.
    findLeaves(root1, leaves1, &index1);
    findLeaves(root2, leaves2, &index2);

    // If the number of leaves is different, the trees are not leaf-similar.
    if (index1 != index2) return false;

    // Compare the leaf sequences.
    for (int i = 0; i < index1; i++) {
        if (leaves1[i] != leaves2[i]) return false;
    }

    return true;
}