【MEDIUM】Find Leaves Of Binary Tree

# 问题

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]

1
/ \
2   3
/ \
4   5

Output: [[4,5,3],,]
``````

Explanation:

``````1. Removing the leaves [4,5,3] would result in this tree:

1
/
2

2. Now removing the leaf  would result in this tree:

1

3. Now removing the leaf  would result in the empty tree:

[]         ``````

# 分析过程

• 输入：一棵二叉树
• 输出：每次移除所有子节点，直到整棵树都是空的
• 思路：递归判断节点是否是叶节点，对根节点就是叶节点的情况单独处理，详细见注释。

# 解决方法

``````class Solution {
public:

void _findLeaves(TreeNode *super, TreeNode *node, int level, vector<vector<int>>& vec) {
if (!node) {
return;
}
// 判断是否是叶节点
if (!node->left && !node->right) {
// 是叶节点，分别看是父节点的左还是右节点，分别处理
if (super->left == node) {
super->left = nullptr;
} else if (super->right == node) {
super->right = nullptr;
}
vec[level].push_back(node->val);
} else {
// 不是叶节点的话，继续递归
_findLeaves(node, node->left, level, vec);
_findLeaves(node, node->right, level, vec);
}
}

vector<vector<int>> findLeaves(TreeNode* root) {
vector<vector<int>> vec;
if (!root) {
return vec;
}
int level = 0;
while (root->left || root->right) {
vec.push_back({});
// 分别对左右子树进行剥离
_findLeaves(root, root->left, level, vec);
_findLeaves(root, root->right, level, vec);
level++;
}
vec.push_back({ root->val });

return vec;
}
};``````

Thanks for reading.

All the best wishes for you! 💕