10. Find Leaves of Binary Tree

Link to the problem

Description

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example

Input: [1,2,3,4,5], Output: [4, 5, 3], [2], [1]

Idea

Define level of a node to be 0 if it's a leaf, and 1 plus the maximum of left/right level otherwise.
Recursively compute the node's level, and put each value in the corresponding level.

Solution

class Solution {
private:
    int getLeaves(TreeNode *root, vector<vector<int> > &leaves) {
        if (!root) return 0;
        int level = (root->left || root->right) ? 1 + max(getLeaves(root->left, leaves), getLeaves(root->right, leaves)) : 0;
        if (level == leaves.size()) leaves.push_back(vector<int> {root->val});
        else leaves[level].push_back(root->val);
        return level;
    }
public:
    vector<vector<int> > findLeaves(TreeNode *root) {
        vector<vector<int> > leaves;
        getLeaves(root, leaves);
        return leaves;
    }
};

68 / 68 test cases passed.
Runtime: 3 ms