# 366. Find Leaves of Binary Tree 寻找二叉树的叶子节点

@TOC

## # 题目描述

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

DFS时遍历的方式选用的后序遍历，因为按照题目的要求，必须从左到右依次放入叶子节点，故遍历方式是`左孩子->右孩子->根节点`

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;
};
``````

## # 日期

2019 年 9 月 24 日 —— 梦见回到了小学，小学已经芳草萋萋破败不堪