865. Smallest Subtree with all the Deepest Nodes
Given the root of a binary tree, the depth of each node is the shortest distance to the root.
Return the smallest subtree such that it contains all the deepest nodes in the original tree.
A node is called the deepest if it has the largest depth possible among any node in the entire tree.
The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
|
class Solution { public: TreeNode* subtreeWithAllDeepest(TreeNode* root) { if(!root) return root; if(!root->right and !root->left) return root; unordered_map<TreeNode*, TreeNode*> parentMap; queue<TreeNode*> q; unordered_set<TreeNode*> deepNodes{root}; q.push(root); while(!q.empty()) { int sz = q.size(); unordered_set<TreeNode*> temp; while(sz--) { auto n = q.front(); q.pop(); if(n->left) { parentMap[n->left] = n; temp.insert(n->left); q.push(n->left); } if(n->right) { parentMap[n->right] = n; temp.insert(n->right); q.push(n->right); } } if(!temp.empty()) swap(deepNodes, temp); } while(deepNodes.size() != 1) { unordered_set<TreeNode*> parentNode; for(auto n : deepNodes) { parentNode.insert(parentMap[n]); } swap(parentNode, deepNodes); }
return *deepNodes.begin(); } };
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
class Solution { pair<int, TreeNode*> findDeep(TreeNode* node, int depth) { if(!node) return {0, node}; auto l = findDeep(node->left, depth + 1), r = findDeep(node->right, depth + 1); return {max(l.first, r.first) + 1, l.first == r.first ? node : l.first > r.first ? l.second : r.second}; } public: TreeNode* subtreeWithAllDeepest(TreeNode* root) { return findDeep(root, 0).second; } };
|