/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
map<int, TreeLinkNode*> rec;
void dfs(TreeLinkNode *root, int dep) {
if (!root) return;
if (rec[dep]) {
rec[dep]>next = root;
}
rec[dep] = root;
dfs(root>left, dep + 1);
dfs(root>right, dep + 1);
}
void connect(TreeLinkNode *root) {
dfs(root, 0);
}
};
Share my concise dfs solution


@cooper said in Share my concise dfs solution:
ses O(log n) extra s
Can I ask why it is O(log n), while I see is O(n) space.

@Acekkkkkkkkk The extra space is due to the hashmap rec, whose size of keys is determined by the depth of the tree, aka log n.

@cooper Thanks, you are right. But just talk a little bit deeper, I think the worst case is log(n) which is a full binary tree, the best case is O(n) with only one node on each level.