二叉樹最大路徑總和，非遞歸，超過時間限制

我正在努力解決這個問題，我想以非遞歸方式解決這個問題。在我的算法中似乎沒有邏輯錯誤，通過了73％的測試用例。但它無法處理大數據，報告「超出時間限制」。我很感激，如果有人可以給我一些提示如何在非遞歸的情況下做到這一點，並避免超時，請提前致謝！二叉樹最大路徑總和，非遞歸，超過時間限制

問題鏈接

我相信也有一個類似的本文給出了。

http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum-ii/

問題描述：

給定一個二叉樹，找到根的最大路徑總和。該路徑可能在樹中的任何節點處結束，並且至少包含一個節點。

實施例：

鑑於下面二叉樹：

/\

回報4.（1-> 3）

法官

時間超出限制

總運行時間：1030毫秒

輸入輸入數據

{-790，-726,970,696，-266，-545,830，-866,669，-488，-122,260,116,521，-866，-480，-573，-926,88,733，＃，＃，483，-935，-285， -258,892,180,279，-935,675,2,596,5,50,830，-607，-212,663,25，-840，＃，＃， - 333754，＃817842，-220，-269,9，-862，-78，-473,643,536 ，-142,773,485,262,360,702，-661,244，-96，＃519566，-893，-599,126，-314,160,358,159，＃，＃， - 237，-522，-327,310，-506,462，-705,868，-782,300，-945，-3,139 ，-193，-205，-92,795，-99，-983，-658，-114，-706,987,292，＃234，-406，-993，-863,859,875,383，-729，-748，-258,329,431，-188， -375，-696，-856,825，-154，-398，-917，-70,105,819，-264,993,207,21，-102,50,569，-824，-604,895，-564，-361,110，-965，-11,557，＃，202213，-141,759,214,207,135,329,15，＃，＃，244＃，334628509627，-737，-33，-339，-985,349,267，-505，-527,882，-352，-357，-630,782，-215，-555,132 ，-835，-421,751,0，-792，-575，-615，-690,718,248,882，-606，-53,157,750,862，＃，940,160,47，-347，-101，-947,739,894，＃， - 658，-90， -277，-925,997,862，-481，-83,708,706,686，-542,485,517，-922,978，-464，-923,710，-691,168，-607，-888，-439,499,794，-601,43 5，-114，-337,422，＃， - 855，-859,163，-224,902，＃，577，＃， - 386,272，-9 ...

預計

我的代碼 C++

/** 
* Definition of TreeNode: 
* class TreeNode { 
* public: 
*  int val; 
*  TreeNode *left, *right; 
*  TreeNode(int val) { 
*   this->val = val; 
*   this->left = this->right = NULL; 
*  } 
* } 
*/ 
class Solution { 
public: 
    /** 
    * @param root the root of binary tree. 
    * @return an integer 
    */ 
    int maxPathSum2(TreeNode *root) { 
     if (root == NULL) return 0; 
     findLeaf(root); 
     return global_max; 
    } 

private: 
    int global_max = INT_MIN; 

    void findLeaf(TreeNode* root) { 
     unordered_map<TreeNode*, TreeNode*> parent; 
     stack<TreeNode*> traverse; 
     parent[root] = NULL; 
     traverse.push(root); 

     while(!traverse.empty()) { 
      TreeNode* p = traverse.top(); 
      traverse.pop(); 
      if (!p->left && !p->right) { 
       findPathMaxSum(p, parent); 
      } 
      if (p->right) { 
       parent[p->right] = p; 
       traverse.push(p->right); 
      } 
      if (p->left) { 
       parent[p->left] = p; 
       traverse.push(p->left); 
      } 
     } 
    } 

    void findPathMaxSum(TreeNode* leaf, unordered_map<TreeNode*, TreeNode*> parent) { 
     TreeNode* current = leaf; 
     stack<TreeNode*> stk; 
     int path_max = INT_MIN; 
     int path_sum = 0; 

     while (current) { 
      stk.push(current); 
      current = parent[current]; 
     } 

     while (!stk.empty()) { 
      current = stk.top(); 
      stk.pop(); 
      path_sum += current->val; 
      path_max = path_max > path_sum ? path_max : path_sum; 
     } 

     global_max = global_max > path_max ? global_max : path_max; 
    } 
};

解決

我接受@Dave Galvin的建議，它的工作原理！下面的代碼：

/** 
* Definition of TreeNode: 
* class TreeNode { 
* public: 
*  int val; 
*  TreeNode *left, *right; 
*  TreeNode(int val) { 
*   this->val = val; 
*   this->left = this->right = NULL; 
*  } 
* } 
*/ 
class Solution { 
public: 
    /** 
    * @param root the root of binary tree. 
    * @return an integer 
    */ 
    int maxPathSum2(TreeNode *root) { 
     if (root == NULL) return 0; 
     int global_max = INT_MIN; 
     stack<TreeNode*> traverse; 
     traverse.push(root); 
     while(!traverse.empty()) { 
      TreeNode* p = traverse.top(); 
      global_max = global_max > p->val ? global_max : p->val; 
      traverse.pop(); 
      if (p->right) { 
       traverse.push(p->right); 
       p->right->val += p->val; 
      } 
      if (p->left) { 
       traverse.push(p->left); 
       p->left->val += p->val; 
      } 
     } 
     return global_max; 
    } 
};

來源

2016-09-24 xman

爲什麼它是必須非遞歸？ – Tempux

@ sudomakeinstall2我只是想以非遞歸的方式嘗試它.... – xman

你能提供鏈接到問題的來源嗎？ –

從上往下，通過向其添加父代的值來更新每個節點。跟蹤你的最大值和位置。最後返回。上）。例如，如果你的二叉樹是T = [ - 4,2,6，-5,2,1,5]，那麼我們將它更新爲： [-4,2-4 = -2,6 -4 = 2，-2-5 = -7，-2 + 2 = 4,2 + 3 = 3,2 + 5 = 7]

這裏的答案是7，即-4,6,5。

來源

2016-09-24 15:20:40 Dave

非常感謝你！有用！！！ AC !!! – xman

編輯：

你不需要findPathMaxSum功能。我也更改了父母的地圖。現在它存儲2個值：

指針父從根
路徑總和爲當前節點。

這是代碼。

class Solution { 
public: 
    /** 
    * @param root the root of binary tree. 
    * @return an integer 
    */ 
    int maxPathSum2(TreeNode *root) { 
     if (root == NULL) return 0; 
     findLeaf(root); 
     return global_max; 
    } 

private: 
    int global_max = INT_MIN; 

    void findLeaf(TreeNode* root) { 
     unordered_map<TreeNode*, std::pair<TreeNode*,int> > parent; 
     stack<TreeNode*> traverse; 
     parent[root] = make_pair(NULL,root->val); 
     traverse.push(root); 

     while(!traverse.empty()) { 
      TreeNode* p = traverse.top(); 
      traverse.pop(); 
      if (!p->left && !p->right) { 
       // findPathMaxSum(p, parent); 
       global_max=std::max(global_max,parent[p].second); 
      } 
      if (p->right) { 
       parent[p->right] = make_pair(p, (p->right->val) +parent[p].second) ; 
       traverse.push(p->right); 
      } 
      if (p->left) { 
       parent[p->left] = make_pair(p, (p->left->val) +parent[p].second) ; 
       traverse.push(p->left); 
      } 
     } 
    };

OLD：

你想通過參考不是值在findPathMaxSum通過地圖。

void findPathMaxSum(TreeNode* leaf, unordered_map<TreeNode*, TreeNode*> parent)

更改爲。

void findPathMaxSum(TreeNode* leaf, unordered_map<TreeNode*, TreeNode*>& parent)

它使你的時間複雜度O（n * n）。

其運行復雜度將變爲O（n * log n）。雖然它不能解決問題，因爲你的約束更緊張。所以我上面發佈了一個O（n）解決方案。

來源

2016-09-24 14:58:50 v78

不，它不會改變任何內容...並且通過引用不會影響時間複雜度。 – xman

請張貼問題的鏈接。經過引用總是做這份工作。 – v78

*「通過引用傳遞總是完成這項工作」* - 像這樣的一攬子報表很容易失效，只有一個反例。確保您的陳述在嘗試簡化時不會出錯。 – IInspectable

我想你的代碼的問題是，當你遍歷你的樹時，你正在迭代每個節點來計算最大路徑。最終的複雜度爲O(n^2)。您需要計算流量上的最大路徑（在遍歷樹時）。

在下面的解決方案中，我使用了here的後序迭代算法。請原諒我用這個而不是你的。

將該溶液（O(n)）僅僅是一個字段max_path添加到每個節點，並且當來訪實際節點採取left和right之間的最大：

void postOrderTraversalIterative(BinaryTree *root) { 
    if (!root) return; 
    stack<BinaryTree*> s; 
    s.push(root); 
    BinaryTree *prev = NULL; 
    while (!s.empty()) { 
     BinaryTree *curr = s.top(); 
     if (!prev || prev->left == curr || prev->right == curr) { 
      if (curr->left) 
       s.push(curr->left); 
      else if (curr->right) 
       s.push(curr->right); 
     } else if (curr->left == prev) { 
      if (curr->right) 
       s.push(curr->right); 
     } else { 
      //Visiting the node, calculate max for curr 
      if (curr->left == NULL && curr->right==NULL) 
       curr->max_path = curr->data; 
      else if (curr->left == NULL) 
       curr->max_path = curr->right->max_path + curr->data; 
      else if (curr->right == NULL) 
       curr->max_path = curr->left->max_path + curr->data; 
      else //take max of left and right 
       curr->max_path = max(curr->left->max_path, curr->right->max_path) + curr->data; 
      s.pop(); 
     } 
     prev = curr; 
    } 
}

來源

2016-09-24 15:42:00

我認爲你是對的，最好是添加一個字段並比較而不是改變節點的實際價值。現在時間複雜度是線性的:) – xman

二叉樹最大路徑總和，非遞歸，超過時間限制

回答

相關問題