对于给定的二叉树，发现这也是二叉搜索树的最大子树？

例如：

输入：

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

输出：

  50
                  / \
                 25 75
                / \ /
               15 35 65
 

解决方案

这答案previously包含一个O基于链路/砍树（N log n）的算法。下面是一个简单的 O（N）解决方案。

的核心是一个接受节点的步骤，根在其左子的独特最大BSST，独特的最大BSST扎根在其右子，和指向最左边和最右边的这些BSSTs的元素。它破坏了其输入（可避免持续性的数据结构），并与它的最小和最大的元素构建了独一无二的最大BSST植根于特定的节点，共同提高。所有BSST节点都标注了后代的数量。像以前一样，这个过程被重复地从一个后序遍历调用。要恢复的子树，记得最大BSST的根;重建它只需要简单的穿越。

我只把左BSST;右侧是对称的。如果左侧BSST的根大于新的根，那么整个子树被移除，并且新的根现在最左边。否则，老最左边的节点仍然最左边。从左侧BSST的最右边的节点开始和向上移动，查找小于或等于所述根的第一个节点。它的右子必须拆除;现在注意，由于BST财产的没有其他节点需要去！的继续向左BSST的根，更新计数，以反映删除。

这之所以是O（n）是，尽管在循环的，在原来的树中的每个边在本质上是遍历只有一次。

编辑：统称走过的路径是在一个BST的最大直线路径，除了左脊椎和右侧脊柱。例如，在输入

  ^ h
             / \
            / \
           / \
          / \
         / \
        / \
       / \
      D L
     / \ / \
    / \ / \
   / \ / \
  乙˚FĴÑ
 / \ / \ / \ / \
A C E G I K M O对
 

这里的每台边缘走过的递归调用：

  ^ h
             / \
            / \
           / \
          / \
         / \
        / \
       / \
      D L
     / H H \
    / H H \
   / H H \
  乙˚FĴÑ
 / D D H H L L \
A C E G I K M O对
 

For a given binary tree, find the largest subtree which is also binary search tree?

Example:

Input:

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

Output:

                   50
                  /   \
                 25   75
                / \   /
               15 35  65

This answer previously contained an O(n log n) algorithm based on link/cut trees. Here is a simpler O(n) solution.

The core is a procedure that accepts a node, the unique maximum BSST rooted at its left child, the unique maximum BSST rooted at its right child, and pointers to the left-most and right-most elements of these BSSTs. It destroys its inputs (avoidable with persistent data structures) and constructs the unique maximum BSST rooted at the given node, together with its minimum and maximum elements. All BSST nodes are annotated with the number of descendants. As before, this procedure is called repeatedly from a post-order traversal. To recover the sub-tree, remember the root of the largest BSST; reconstructing it requires only a simple traversal.

I'll treat the left BSST only; the right is symmetric. If the root of the left BSST is greater than the new root, then the entire sub-tree is removed, and the new root is now left-most. Otherwise, the old left-most node is still left-most. Starting from the right-most node of the left BSST and moving upward, find the first node that is less than or equal to the root. Its right child must be removed; note now that due to the BST property, no other nodes need to go! Proceed to the root of the left BSST, updating the counts to reflect the deletion.

The reason this is O(n) is that in spite of the loop, each edge in the original tree is in essence traversed only once.

EDIT: collectively, the paths traversed are the maximal straight-line paths in a BST, except for the left spine and the right spine. For example, on the input

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

here are the recursive calls on which each edge is traversed:

              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