Share my concise dfs solution


  • 3
    O
    /**
     * 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);
        }
    };

  • 0
    C

    This is nice and concise, but it uses O(log n) extra space.


  • 0
    O

    Yes. Is there a way which don't use any extra space?

    I also know the bfs solution for this problem but we also need to maintain a queue.


  • 0
    C

    Yes, but by BFS you can solve it using constant extra space.

    I don't know if there is a way to solve it without using any extra space, my guess is no.


  • 0
    O
    This post is deleted!

  • 0
    A

    @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.


  • 0
    C

    @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.


  • 0
    A

    @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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.