BST的第二个最大值

Question

这是一个面试问题.在BST中找到第二个最大值.

最大元素是BST中最右边的叶子.第二个最大值是其父或其左子.因此解决方案是遍历BST以找到最右边的叶子并检查其父和左子.

是否有意义？

Answer 1

不,那是错的.考虑一下这个BST:

        137
       /
      42
       \
        99

这里,第二个到最大值是最大值的左子节点的最右边的子节点.您的算法需要更新,以便检查最大值的父级,或最大的左子级的最右侧子级.

另请注意,max不一定是最右边的叶节点,它是树的右脊椎底部的节点.上面,137不是叶子.

希望这可以帮助!

Answer 2

回想一下,您可以通过执行修改后的遍历遍历来以相反的顺序列出BST的节点,其中您首先探索正确的子树.这导致了一个简单的算法:

Node rightmost = findRightmostNode(root)
if (rightmost.left != null) {
    return findRightmostNode(rightmost.left)
else{
    return rightmost.parent
}

如果树只有一个元素,它将返回null.

Answer 3

public static int findSecondLargestValueInBST(Node root)
    {
        int secondMax;
        Node pre = root;
        Node cur = root;
        while (cur.Right != null)
        {
            pre = cur;
            cur = cur.Right;
        }
        if (cur.Left != null)
        {
            cur = cur.Left;
            while (cur.Right != null)
                cur = cur.Right;
            secondMax = cur.Value;
        }
        else
        {
            if (cur == root && pre == root)
                //Only one node in BST
                secondMax = int.MinValue;
            else
                secondMax = pre.Value;
        }
        return secondMax;
    }

Answer 4

算法可以如下

1. find the largest number in the tree. 

  private static int findLargestValueInTree(Node root) {
    while (root.right != null) {
     root = root.right;
    }
    return root.data;
  }

2. Find the largest number in the tree that is smaller than the number we found in step 1

 public static int findSecondLargest(Node root, int largest, int current) {
   while (root != null) {
    if (root.data < largest) {
      current = root.data;
      root = root.right;
    } else {
      root = root.left;
   }
   }
  return current;
 }

'current'跟踪当前最大的数字,该数字小于step1中的数字

Answer 5

具有时间复杂度O(logN)和空间复杂度O(1)的更简单的迭代方法

public static void main(String[] args) {    
        BinaryTreeNode result=isBinarySearchTree.secondLargest(rootNode);

            System.out.println(result.data);
        }

        private BinaryTreeNode secondLargest(BinaryTreeNode node) {

            BinaryTreeNode prevNode=null; //2nd largest Element
            BinaryTreeNode currNode=node;
            if(null == currNode)
                return prevNode;

            while(currNode.right != null){
                prevNode=currNode;
                currNode=currNode.right;
            }
            if(currNode.left != null){
                currNode=currNode.left;
                while(currNode.right != null){
                    currNode=currNode.right;
                }
                prevNode=currNode;
            }

            return prevNode;

        }