algoadvance

Leetcode 872. Leaf

Problem Statement

The problem “Leaf-Similar Trees” from LeetCode asks that you determine if two binary trees are “leaf-similar.” Two trees are considered leaf-similar if their leaf value sequence is the same. The sequence is the list of leaf values when traversing the tree left to right.

Example:

  Tree 1:     Tree 2:
     3           4
    / \         / \
   5   1       2   7
      / \
     6   2

Tree 1 leaves: [5, 6, 2]
Tree 2 leaves: [2, 7, 2]

Not leaf-similar since [5, 6, 2] != [2, 7, 2]

Constraints:

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

Clarifying Questions

  1. Definition of a leaf node: A leaf node is a node that doesn’t have any children.
  2. Input format: Two binary trees will be provided as inputs.
  3. Output specification: We need to output true or false based on whether the trees are leaf-similar.

Strategy

  1. In-order Traversal: We will perform an in-order traversal (left, node, right) on both trees and record the leaf values.
  2. Comparison of Arrays: Compare the resultant arrays of leaf values from both trees to determine if they are similar.

Steps:

  1. Implement a helper function to traverse the tree and record the leaf nodes.
  2. Implement the main function to call the helper for both trees and compare the results.

Code Implementation

#include <vector>
#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    void getLeaves(TreeNode* root, std::vector<int>& leaves) {
        if (root == NULL) {
            return;
        }
        if (root->left == NULL && root->right == NULL) {
            leaves.push_back(root->val);
        }
        getLeaves(root->left, leaves);
        getLeaves(root->right, leaves);
    }
    
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        std::vector<int> leaves1, leaves2;
        getLeaves(root1, leaves1);
        getLeaves(root2, leaves2);
        return leaves1 == leaves2;
    }
};

Time Complexity

The time complexity of this solution is O(n + m), where n is the number of nodes in the first tree and m is the number of nodes in the second tree. This is because we traverse each tree once to collect the leaf nodes.

The space complexity is O(L1 + L2), where L1 and L2 are the number of leaf nodes in the first and second tree, respectively. This is for storing the leaf nodes in two vectors. If we consider the recursion stack, it can also go up to O(h1 + h2) where h1 and h2 are the heights of the trees.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI