今天面试被问到：找到二叉树中两个元素最近的后代

Question

只是想知道我在今天的面试中是否做对了。设置是

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

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

例如

     5
    / \ 
   4   6
  / \   \ 
 2   3   7

ClosestDesendant 的 left 和 right 节点的 val 2 和 7将是 5，left 和 right 节点的 ClosestDesendant 的 val 具有 vals 2 和 3 将是 4.

我的实现是

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

我想知道

• 这是正确的吗？
• 这是双向飞碟认证的吗？
• 什么是更好的解决方案？

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