c - 二分木で一番左のノードを見つける

Question

二分木で一番左のノードを見つける必要があります。素朴に聞こえるかもしれませんが、そうではありません。私はこれを試しましたが、失敗すると思います：

Node* findLeftMostNode(Node* root){
    if(root->left==null)
       return root;
    findLeftMostNode(root->left);
}

問題は、左モード ノードが任意のレベルにある可能性があるため、それを処理する必要があることです。

          X
          \
           X
           /\
          X  X
         /
        X
       /
      X

Answer 1

ノードの「左さ」を計算するこの方法では、常に両方の子ノードに再帰する必要があります。これは、任意のn に対して左に行くnノードのシーケンスを任意の子に含めることができるためです。

したがって、解決策は実際には非常に単純です。ツリー内の各ノードの x を計算し、最小のものを返します。

Node* findLeftmostNode(Node* current, int x = 0)
{
    current->x = x;

    Node* best;
    // leftmost child in the left subtree is always better than the root
    if (current->left == null)
        best = current;
    else
        best = findLeftmostNode(current->left, x - 1);

    if (current->right != null)
    {
        Node* found = findLeftmostNode(current->right, x + 1);
        if (found->x < best->x)
            best = found;
    }

    return best;
}

Answer 2

Node *findLeftMostNode(Node* root){
    for( ; root; root =root->left)
    if (!root->left) break;
    }
  return root;
}