LeetCode 366. Find Leaves of Binary Tree

實質就是求每個節點的最大深度。用一個hash表記錄，最后輸出。

class Solution {
public:unordered_map<TreeNode *,int> hash; // record the level from bottom
    vector<vector<int>> findLeaves(TreeNode* root) {vector<vector<int>> res;dfs(root);//for (auto x:hash) cout << x.first->val << ' ' << x.second << endl;for (int i=1;i<=hash[root];++i){vector<int> tmp;for (auto x:hash){if (x.second==i)tmp.push_back(x.first->val);}res.push_back(tmp);}return res;}int dfs(TreeNode *root){if (root==NULL) return 0;int depth=max(dfs(root->left),dfs(root->right))+1;hash[root] = depth;return depth;}
};

?

其實可以不用hash表，每次深度比vector.size()大的時候新建一個vector，這樣節省了空間。

類似的方法在別的題里也有應用。

class Solution {
public:vector<vector<int>> res;vector<vector<int>> findLeaves(TreeNode* root) {dfs(root);return res;}int dfs(TreeNode *root){if (root==NULL) return 0;int depth=max(dfs(root->left),dfs(root->right))+1;if (depth>res.size()) res.push_back(vector<int>());res[depth-1].push_back(root->val);return depth;}
};

?