algorithm - 对于给定的二叉树找到最大的二叉搜索子树

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) 解决方案。

核心是一个过程，它接受一个节点、以其左 child 为根的唯一最大 BSST、以其右 child 为根的唯一最大 BSST，以及指向这些 BSST 最左边和最右边元素的指针。它销毁其输入(可通过持久数据结构避免)并构造以给定节点为根的唯一最大 BSST 及其最小和最大元素。所有 BSST 节点都标有后代数。和以前一样，从后序遍历中重复调用此过程。要恢复子树，记住最大 BSST 的根；重构它只需要一个简单的遍历。

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

这是 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