题目地址：https://leetcode-cn.com/problems/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],[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:
[]
题目大意
给你一棵完全二叉树，请按以下要求的顺序收集它的全部节点：
- 依次从左到右，每次收集并删除所有的叶子节点
- 重复如上过程直到整棵树为空
解题方法
DFS
我的做法比较新颖：计算每个节点的高度，依次放入高度为0,1,2,...,depth(root)的所有节点。
为什么？因为题目虽然让我们每次放入的都是叶子节点，而叶子节点的高度是0。当删除叶子节点时，会使剩余的每个节点的高度减一，此时新的叶子节点就是如果不删除老叶子节点时高度为1的节点……按照这个方法去做，就是依次放入高度为0,1,2,...,depth(root)的所有节点。
求树的高度用到了记忆化搜索，即代码中的node2depth，这是为了保存已经计算过高度的叶子节点，从而加速求树的高度的计算。
保存每个高度对应了哪些叶子节点的值，使用的是倒排表depth2node，其key是高度，value是该高度下对应的叶子节点的值。
DFS时遍历的方式选用的后序遍历，因为按照题目的要求，必须从左到右依次放入叶子节点，故遍历方式是左孩子->右孩子->根节点。
这个做法的好处是不用修改树的结构，比如做删除叶子节点的操作。
时间复杂度是O(N)，N为节点数。
C++代码如下：
/**
* 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:
vector<vector<int>> findLeaves(TreeNode* root) {
vector<vector<int>> res;
int height = depth(root);
for (int i = 0; i <= height; ++i) {
res.push_back(depth2node[i]);
}
return res;
}
int depth(TreeNode* root) {
if (!root) return -1;
if (node2depth.count(root))
return node2depth[root];
int left = depth(root->left);
int right = depth(root->right);
int cur = max(left, right) + 1;
depth2node[cur].push_back(root->val);
node2depth[root] = cur;
return cur;
}
private:
unordered_map<int, vector<int>> depth2node;
unordered_map<TreeNode*, int> node2depth;
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发