algoadvance

Leetcode 872. Leaf

Problem Statement

Given two binary trees, return true if and only if they have the same leaf node sequence. Leaf nodes are defined as nodes with no children.

Example:

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:
The leaf sequence from both trees is [6, 7, 4, 9, 8].

Clarifying Questions

  1. How should the input trees be represented?
    • The trees will be given as root nodes of TreeNode objects.
  2. What should be returned if both trees are empty?
    • If both trees are empty, they are considered to have the same leaf sequence, so return true.
  3. What if only one of the trees is empty?
    • If only one tree is empty, they cannot have the same leaf sequence, so return false.

Strategy

To determine if two trees have the same leaf sequence, we can:

  1. Implement a helper function to find the leaf nodes of a given tree.
  2. Traverse both trees using a depth-first search (DFS) to collect their leaf nodes.
  3. Compare the two sequences of leaf nodes.

Code

Here’s how you can implement this in Java:

/**
 * 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 {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leaves1 = new ArrayList<>();
        List<Integer> leaves2 = new ArrayList<>();
        
        getLeaves(root1, leaves1);
        getLeaves(root2, leaves2);
        
        return leaves1.equals(leaves2);
    }
    
    private void getLeaves(TreeNode root, List<Integer> leaves) {
        if (root == null) {
            return;
        }
        
        if (root.left == null && root.right == null) {
            leaves.add(root.val);
        }
        
        getLeaves(root.left, leaves);
        getLeaves(root.right, leaves);
    }
}

Time Complexity

Explanation

  1. getLeaves: This helper function recursively traverses the tree using DFS. When it encounters a leaf node (both left and right children are null), it adds the leaf node’s value to the list.
  2. leafSimilar: This function initializes two lists to store the leaves of each tree, calls getLeaves for both root nodes, and finally checks if the two lists are equal. If they are, the trees have the same leaf node sequence; otherwise, they don’t.

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