在Java中實現的二叉樹LCA的時間複雜度是多少

我有這段代碼可以找到binary tree中兩個nodes的least common Ancestor。我認爲時間複雜度是O(log n)。但需要專家意見。這段代碼在我的輸入上工作得很好，但我不確定我是否已經詳盡地進行了測試。在Java中實現的二叉樹LCA的時間複雜度是多少

這裏是代碼

//LCA of Binary tree 
     public static Node LCABT(Node root, int v1, int v2){ 
      if (root==null) 
       return null; 
      if (root.data==v1 || root.data==v2){ 
       return root; 
      } 
      Node left = LCABT(root.left,v1,v2); 
      Node right = LCABT(root.right,v1,v2); 

      if(left!=null && right!=null) 
       return root; 
      else if (left!=null) 
       return left; 
      else return right; 
     }

來源

2014-01-29 brain storm

我敢肯定，這個運行在O (n)因爲你穿過整個圖形（即在每一個節點，你會在兩個方向上 - 左，右）。我建議您閱讀Tarjan's off-line lowest common ancestors algorithm。

來源

2014-01-29 06:36:46 Mihai238

您的代碼的時間複雜度爲O(n)，因爲您正在遍歷整棵樹，即您正在訪問其所有節點。但是，如果您沒有BST，而只是一棵二叉樹，那麼無需在父節點上指針即可實現最佳效果（在這種情況下，構建從兩個節點到根節點的路徑並返回一個在兩條路徑中）。如果您有BST，則可以找到兩個節點，並在O(h)中查找最小公共祖先，其中h是樹的高度，如果樹是平衡的，則爲O(log n)。

最後的評論 - 如果你正在準備比賽或面試，請務必照顧角落案件。您的代碼不處理樹中未包含其中一個節點的情況。

來源

2014-01-29 07:59:29

它提到了你提到的角落案例，你怎麼認爲它沒有？ –

@ user1988876好吧，如果在樹的左邊部分有'v1'，而'v2'根本不在樹中，那麼無論是否存在'v2'，都會返回'v1'。有人可能會爭辯說，在這種情況下，它也應該返回'null'。如果兩個節點都不包含在樹中，那麼你返回'null'，這是正確的 - 我會更新我的答案。 –

這是正確的。這意味着在我調用這個方法之前我需要檢查這些是否存在，或者我有辦法在這裏處理它嗎？ –

在Java中實現的二叉樹LCA的時間複雜度是多少

回答

相關問題