recursion - 二分木ノードの深さを非再帰的に取得する

Question

再帰を使用せずに、バイナリツリー（バランスの取れたもの、またはBSTではない）のノードの深さを取得する方法を誰かが指摘できますか？理想的にはJava/C / C＃で

ノードは次のように表されます。

class Node
{
  Node Left;
  Node Right;
  string Value;
  int Depth;
}

FIFOリストでレベル順序を使用することは私の最初の考えでしたが、特に不均衡なツリーの場合、レベルがいつ変化するかを検出することに困惑しました。

Answer 1

スタックを使用して再帰メソッドを実装できます。これが、とにかく再帰がどのように機能するかです。再帰関数が次のようになっていると想像してください

function int getDepth (Node head, string val)
{
    if (head == NULL)
        return -1;

    if (val == head.Value)
        return head.Depth;

    return MAX(getDepth(head.Left, val), getDepth(head.Right, val);
}

非再帰関数は次のようになります

function int getDepth (Node head, string val)
{
    Stack s = new Stack();

    s.push(head);

    while(s.count > 0)
    {
        Node temp = s.pop();

        if (temp != NULL)
        {
            if (s.Value == val)
                return s.Depth;
            else
            {
                s.push(temp.Left);
                s.push(temp.Right);
            }
        }

    }


    return -1;
}

編集：

この関数は、各ノードの深さを設定します

function void setDepth (Node head)
{
    Stack s = new Stack();

    head.Depth = 0;
    s.push(head);

    while(s.count > 0)
    {
        Node temp = s.pop();

        if (temp != NULL)
        {
            if (temp.Left != NULL)
            {
                temp.Left.Depth = temp.Depth + 1;
                s.push(temp.Left);
            }

            if (temp.Right != NULL)
            {
                temp.Right.Depth = temp.Depth + 1;
                s.push(temp.Right);
            }
        }

    }

}

Answer 2

ノードの深さの値を入力すること、および/または最大の深さを見つけることを意味すると思います。これを行う1つの方法は、2つのリストを使用し、提案されているようにレベルの順序を実行することです。それは次のようになります：

int level=0;
List<Node> currentLevel = new List<Node>{root};
while(currentLevel.Count != 0)
{
  List<Node> nextLevel = new List<Node>{};
  foreach(Node node in currentLevel)
  {
    if(node.Right!=null) nextLevel.Add(node.Right);
    if(node.Left != null) nextLevel.Add(node.Left);
    node.Depth=level;
  }
  level++;
  currentLevel=nextLevel;
}

基本的に、特定のレベルで各ノードを列挙してから、次のレベルで各ノードを見つけます。ノード/レベルがなくなるまで。明らかに、リストはデータ構造（リンクリスト、キューなど）のようなほぼすべてのリストに置き換えることができます。そして、「レベル」の最後の値は最大深度+1になります。

質問の再読に基づくもう1つの説明。特定の値を持つノードを検索していて、その深さを見つけたい場合は、foreachループを変更して「if（node.Value == searchValue）returnlevel;」を含めます。また、技術的には、特定の値を検索する場合は、レベル順序トラバーサルを実行するのではなく、関連するバイナリツリープロパティを使用して値を検索する必要があります（例：val <currentNode.Value goto left else goto right）、そしてあなたの深さを追跡します。ノードのみが与えられ、その深さを知りたい場合は、ルートからノードの二分探索を実行するか、ノードの親を追跡する必要があります。

Answer 3

ここにもっと簡単な解決策があると思います。データ構造が任意の数の子を許可する場合、このソリューションはその場合でも簡単に変更できます。

int getDepthNoRecursion(Node n) {
  if(n == null) {
    return 0;
  }
  int retval = 0;
  n.depth = 1;
  Stack s = new Stack();
  s.push(n);
  while(!s.isEmpty()) {
    Node n = (Node) s.pop();
    int currDepth = n.depth;
    if(currDepth > retval) {
      retval = currDepth;
    }
    if(n.left != null) {
      n.left.depth = currDepth + 1;
      s.push(n.left);
    }
    if(n.right != null) {
      n.right.depth = currDepth + 1;
      s.push(n.right);
    }
  }
  return retval;
}
class Node {
  Node left;
  Node right;
  int depth = 0;
}

Answer 4

これが私が思いついた最も効率的なソリューションです（C ++）。秘訣は、2番目のキューを使用して、現在のレベルのすべてのノードの子を格納することです。これは、平衡および不平衡の二分木に対して機能します。

template <class T>
struct TreeNode {
  TreeNode<T>* left_;
  TreeNode<T>* right_;
  T* data_;
};

template <class T>
int find_depth( const TreeNode<T>* root ) {   
  if ( root == NULL ) return 0;
  int depth = 0;
  std::queue<const TreeNode<T>*>* q1 = new std::queue<const TreeNode<T>*>;
  std::queue<const TreeNode<T>*>* q2 = new std::queue<const TreeNode<T>*>;
  q1->push( root );
  while ( !q1->empty() ) {
    // At the top of the outer loop q1 contains a complete horizontal level of the tree                                                                                  
    depth++;

    // Swap the queue pointers to avoid any deep copies                                                                                                                  
    std::queue<const TreeNode<T>*>* tmpQ = q2;
    q2 = q1;
    q1 = tmpQ;

    // Iterate over this level, inserting all children into q1                                                                                                           
    while( !q2->empty() ) {
      const TreeNode<T>* node = q2->front();
      if ( node->left_ != NULL ) q1->push( node->left_ );
      if ( node->right_ != NULL ) q1->push( node->right_ );
      q2->pop();
    }
  }
  delete q1;
  delete q2;
  return depth;
}