今日インタビューで尋ねられました：バイナリツリー内の2つの要素の最も近い子孫を見つけよう

Question

今日私はインタビューでこれを正しく実行したかどうか疑問に思っています。セットアップは

Node ClosestDescendent (Node root, Node left, Node right) 
{ 
    // ... 
} 

class Node 
{ 
    int val; 
    Node left; 
    Node right; 
} 

です。

 5 
    /\ 
    4 6 
/\ \ 
2 3 7 

val S 2と7とleftとrightノードのClosestDesendantのvalため5であろう、そしてval S 2と3は4をあろうとleftとrightノードのClosestDesendantのval 。

私の実装では、私は

• は

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

  、これが正しいと思ったんだけどでしたか？

• このSkeet認定はありますか？
• もっと良い解決策はありますか？

Answer 1

いくつかの擬似コード：オフトピック

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