A different solution, critique needed


  • 0
    D

    I've seen a lot of really simple recursive solutions on the forums. Most of the discussions are the variation around the same solution (which might be the best one, really). However, not everyone thinks intuitively like that and it might be difficult to come up with a solution like that within 45 minutes of an on-site interview. So here is my solution, reached normally within 45 minutes and passes 87/92 test cases after which it TLEs.

    The idea is to do in-order traversal to get all nodes.
    Convert the tree into an DAG (adjList).
    For each node, dfs and find the path with largest sum.
    Return the largest sum.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        void inorder(TreeNode *root, vector<TreeNode *> &list){
            if(!root) return;
        
            inorder(root->left, list);
            list.push_back(root);
            inorder(root->right, list);
        }
    
        void addEdge(TreeNode *u, TreeNode *v, map<TreeNode *, vector<TreeNode *>> &adjList){
    
            if(adjList.find(u) == adjList.end()){
                auto l = vector<TreeNode *>();
                l.push_back(v);
                adjList[u] = l;
            }else{
                auto l = adjList[u];
                l.push_back(v);
                adjList[u] = l;
            }
        
            if(adjList.find(v) == adjList.end()){
                auto l = vector<TreeNode *>();
                l.push_back(u);
                adjList[v] = l;
            }else{
                auto l = adjList[v];
                l.push_back(u);
                adjList[v] = l;
            }
        }
    
        void dfs(TreeNode *n, map<TreeNode *, vector<TreeNode *>> &adjList, int sum,  int &maxr, set<TreeNode *> &visited){
            if(!n) return;
            visited.insert(n);
        
            vector<TreeNode *> neighbors = adjList[n];
            for(auto neighbor: neighbors){
                if(neighbor && visited.find(neighbor) == visited.end()){
                    int s = sum + neighbor->val;
                    maxr = max(maxr, s);
                    visited.insert(neighbor);
                    dfs(neighbor, adjList, s, maxr, visited);
                }
            }
        }
    
        int maxPathSum(TreeNode* root) {
            if(!root) return 0;
        
            if(root->left == NULL && root->right == NULL) return root->val;
        
            vector<TreeNode *> nodes;
            map<TreeNode*, vector<TreeNode*>> adjList; 
        
            inorder(root, nodes); // O(N)
        
            int maxr = INT_MIN;
    
            for(auto n: nodes){ // O(N)
                addEdge(n, n->left, adjList);
                addEdge(n, n->right, adjList);
                maxr = max(n->val, maxr);
            }
        
        
            // double work here u->v, v->u. reduce it. 
            for(auto n: nodes){ // O(N^2)??
                set<TreeNode *> visited;
                int s = n->val;
                int t=INT_MIN;
                dfs(n, adjList, s, t, visited);
                maxr = max(t, maxr);
            }
        
            return maxr;
        }
    };

Log in to reply
 

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