[LeetCode] 366. Find Leaves of Binary Tree #366
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]
1
/ \
2 3
/ \
4 5
Output: [[4,5,3],[2],[1]]
Explanation:
1. Removing the leaves [4,5,3] would result in this tree:
1
/
2
2. Now removing the leaf [2] would result in this tree:
1
3. Now removing the leaf [1] would result in the empty tree:
[]
Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.
这道题给了我们一个二叉树，让我们返回其每层的叶节点，就像剥洋葱一样，将这个二叉树一层一层剥掉，最后一个剥掉根节点。那么题目中提示说要用DFS来做，思路是这样的，每一个节点从左子节点和右子节点分开走可以得到两个深度，由于成为叶节点的条件是左右子节点都为空，所以我们取左右子节点中较大值加1为当前节点的深度值，知道了深度值就可以将节点值加入到结果res中的正确位置了，求深度的方法我们可以参见 Maximum Depth of Binary Tree 中求最大深度的方法，参见代码如下：
解法一：
class Solution {
public:
vector<vector<int>> findLeaves(TreeNode* root) {
vector<vector<int>> res;
helper(root, res);
return res;
}
int helper(TreeNode* root, vector<vector<int>>& res) {
if (!root) return -1;
int depth = 1 + max(helper(root->left, res), helper(root->right, res));
if (depth >= res.size()) res.resize(depth + 1);
res[depth].push_back(root->val);
return depth;
}
};
下面这种DFS方法没有用计算深度的方法，而是使用了一层层剥离的方法，思路是遍历二叉树，找到叶节点，将其赋值为NULL，然后加入leaves数组中，这样一层层剥洋葱般的就可以得到最终结果了：
解法二：
class Solution {
public:
vector<vector<int>> findLeaves(TreeNode* root) {
vector<vector<int>> res;
while (root) {
vector<int> leaves;
root = remove(root, leaves);
res.push_back(leaves);
}
return res;
}
TreeNode* remove(TreeNode* node, vector<int>& leaves) {
if (!node) return NULL;
if (!node->left && !node->right) {
leaves.push_back(node->val);
return NULL;
}
node->left = remove(node->left, leaves);
node->right = remove(node->right, leaves);
return node;
}
};
还有一种不用建立新的递归函数的方法，就用本身来做递归，我们首先判空，然后对左右子结点分别调用递归函数，这样我们suppose左右子结点的所有叶结点已经按顺序存好到了二维数组left和right中，现在要做的就是把两者合并。但是我们现在并不知道左右子树谁的深度大，我们希望将长度短的二维数组加入到长的里面，那么就来比较下两者的长度，把长度存到结果res中，把短的存入到t中，然后遍历短的，按顺序都加入到结果res里，好在这道题没有强行要求每层的叶结点要按照从左到右的顺序存入。当左右子树的叶结点融合完成了之后，当前结点也要新开一层，直接自己组一层，加入结果res中即可，参见代码如下：
解法三：
class Solution {
public:
vector<vector<int>> findLeaves(TreeNode* root) {
if (!root) return {};
vector<vector<int>> left = findLeaves(root->left), right = findLeaves(root->right);
vector<vector<int>> res = (left.size() >= right.size()) ? left : right;
vector<vector<int>> t = (left.size() >= right.size()) ? right : left;
for (int i = 0; i < t.size(); ++i) {
res[i].insert(res[i].begin(), t[i].begin(), t[i].end());
}
res.push_back({root->val});
return res;
}
};
类似题目：
参考资料：
https://leetcode.com/problems/find-leaves-of-binary-tree/