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;
}