再帰的Vs反復的BSTのトラバーサル

Question

Nノードのバイナリツリーの再帰的トラバーサルを実行すると、実行スタックでN個のスペースを占有します。 私は反復を使用する場合、私は明示的なスタックでN個のスペースを使用する必要があります。

質問再帰的なトラバーサルは、反復的なものが使用しているようにO(N)空間の複雑さを使用しているとも言えますか？ 私はメモリ制限によって私を制限するいくつかのプラットフォームでトラバーサルコードを実行するという面で話しています。 また、反復処理を直接実装することについては言及していません（いずれかのアプローチが良いと言えるでしょう）、私はKthSmallestElement()のアルゴリズムをBSTを使って横断検索を実装しています。

スペースの複雑さの点で反復アプローチまたは再帰的アプローチを使用して、コードがスペース制限内で失敗しないようにする必要がありますか？明らかにそれを置く

：

をここでは、私が実装するものである：ここでは

int Solution::kthsmallest(TreeNode* root, int k) { 
    stack<TreeNode *> S; 
    while(1) 
    { 
     while(root) 
     { 
      S.push(root); 
      root=root->left; 
     } 

     root=S.top(); 
     S.pop(); 

     k--; 
     if(k==0) 
      return root->val; 

     root=root->right; 
    } 
} 

は私の友人が実装するものである：

class Solution { 
    public: 
     int find(TreeNode* root, int &k) { 
      if (!root) return -1; 
      // We do an inorder traversal here. 
      int k1 = find(root->left, k); 
      if (k == 0) return k1; // left subtree has k or more elements. 
      k--; 
      if (k == 0) return root->val; // root is the kth element. 
      return find(root->right, k); // answer lies in the right node. 
     } 

     int kthsmallest(TreeNode* root, int k) { 
      return find(root, k); // Call another function to pass k by reference. 
     } 
}; 

SO 2のどちらがどのように&良いですか？

Answer 1

あなたは、メモリの使用を気にしている場合、あなたはあなたの木がバランス、であることを確認してみてください、すなわちその深さはノード数よりも小さくなります。 N個のノードを有する完全に平衡した二分木は、深さログ N（切り上げ）を有する。

バイナリツリー内のすべてのノードを参照するのに必要なメモリは、誤って考えるほどノードの数ではなく、ツリーの深さに比例するため重要です。再帰的または反復的なプログラムは、以前に訪れた他のノードではなく、ルートから現在のノードへのパスを「記憶」する必要があります。