对于给定的二叉树,找到最大二进制搜索子树

Question

对于给定的二叉树,找到最大的子树,它也是二叉搜索树？

例:

输入:

                   10
               /         \
             50           150
            /  \         /   \
          25    75     200    20
         / \   / \    /  \    / \
        15 35 65 30  120 135 155 250 

输出:

                   50
                  /   \
                 25   75
                / \   /
               15 35  65

Answer 1

该答案之前包含基于链接/切割树的 O(n log n) 算法。这是一个更简单的O(n)解决方案。

核心是一个过程，它接受一个节点、以其左子节点为根的唯一最大 BSST、以其右子节点为根的唯一最大 BSST，以及指向这些 BSST 的最左边和最右边元素的指针。它破坏其输入（可通过持久数据结构避免）并构造以给定节点为根的唯一最大 BSST 及其最小和最大元素。所有 BSST 节点都用后代数量进行注释。和以前一样，这个过程在后序遍历中被重复调用。要恢复子树，请记住最大 BSST 的根；重建它只需要简单的遍历。

我将只处理左侧 BSST；右边是对称的。如果左侧 BSST 的根大于新根，则删除整个子树，并且新根现在位于最左侧。否则，旧的最左边节点仍然是最左边。从左边BSST的最右边的节点开始，向上移动，找到第一个小于或等于根的节点。它的右孩子必须被移除；现在请注意，由于 BST 属性，不需要其他节点！继续到左侧 BSST 的根，更新计数以反映删除。

这是 O(n) 的原因是，尽管有循环，原始树中的每条边本质上只被遍历一次。

编辑：总的来说，所经过的路径是 BST 中的最大直线路径，除了左脊柱和右脊柱之外。例如，在输入上

              H
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      D               L
     / \             / \
    /   \           /   \
   /     \         /     \
  B       F       J       N
 / \     / \     / \     / \
A   C   E   G   I   K   M   O

以下是遍历每条边的递归调用：

              H
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      D               L
     / h             h \
    /   h           h   \
   /     h         h     \
  B       F       J       N
 / d     d h     h l     l \
A   C   E   G   I   K   M   O