Python DFS


  • 0
    class Solution:
        def connect(self, root):
            dic = {}
            def dfs(r, d):
                if not r:
                    return
                if d in dic:
                    dic[d].next = r
                dic[d] = r
                r.next = None
                dfs(r.left, d + 1)
                dfs(r.right, d + 1)
            dfs(root, 0)
    

  • 0

    I had same DFS solution, but it looks like O(logN) space instead of O(1) since the vector size is the maximum depth of the tree.

        vector<TreeLinkNode*> rightNodes;  // index is tree level  
        void connect(TreeLinkNode *r) { connectAtLevel(r); }    
        void connectAtLevel(TreeLinkNode *r, int level = 0) {
            if (!r) return;
            if (rightNodes.size() == level) { r->next = NULL; rightNodes.push_back(r); }
            else { r->next = rightNodes[level];  rightNodes[level] = r; }
            connectAtLevel(r->right, level+1); connectAtLevel(r->left, level+1);
        }
    

Log in to reply
 

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