Bir röportajda bugün sordu: Bir ikili ağaçtaki iki elementin en yakın torununu bulun

Question

Sadece bugün mülakatta bunu doğru yapıp yapmadığımı merak ediyorum. Kurulum,

örn.

 5 
    /\ 
    4 6 
/\ \ 
2 3 7 

val s 2 ve 7 ile left ve right düğüm ClosestDesendant arasında val için 5 olacaktır ve val s 2 ve 34 olur ile left ve right düğüm ClosestDesendant arasında val .

Benim uygulanması ben

• Node ClosestDescendent (Node root, Node left, Node right) 
  { 
      // assume left != right and both left and right are 
      // nodes in the tree 
  
      // figuring out which is the smaller and which is the bigger 
      // simplifies logic later 
      Node smaller, bigger; 
      if (left.val < right.val) { smaller = left; bigger = right; } 
      else { smaller = right; bigger = left; } 
      // traverse tree towards both left and right 
      // until the path diverges 
      Node curnode = root; 
      while (true) 
      { 
       if (curnode.val < smaller.val && curnode.val < bigger.val) 
       { 
        curnode = curnode.right; 
       } 
       else if (curnode.val > smaller.val && curnode.val > bigger.val) 
       { 
        codenode = cornode.left; 
       } 
       else // curnode.val >= smaller.val && curnode.val <= biger.val 
       { 
        break; 
       } 
      } 
      return curnode; 
  } 
  

  ve bu doğru mi merak ediyorum edildi?

• Bu Skeet sertifikalı mı?
• Daha iyi bir çözüm nedir?

Answer 1

Bazı sözde kod:

// TODO: Null check, equality handling. 
Node ClosestDescendent(Node root, Node left, Node right) { 

    const int root_val = root->val; 
    const int left_val = left->val; 
    const int right_val = right->val; 

    // left and right diverges two ways 
    if ((left_val < root_val) && (right_val > root_val)) { 
    return root; 
    } 

    // left and right both are to the left 
    else if ((left_val < root_val) && (right_val < root_val)) { 
    return ClosestDescendent(root->left, left, right); 
    } 

    // left and right both are to the right 
    else ((left_val > root_val) && (right_val > root_val) { 
    return ClosestDescendent(root->right, left, right); 
    }  
}