对于给定的二叉树，找到最大的子树，它也是二叉树吗？
例子:
输入:
10
/ \
50 150
/ \ / \
25 75 200 20
/ \ / \ / \ / \
15 35 65 30 120 135 155 250
输出:
50
/ \
25 75
/ \ /
15 35 65
最佳答案
该答案先前包含基于链接/剪切树的O(n log n)算法。这是一个更简单的 O(n)解决方案。
核心是一个程序，它接受一个节点，以其左子节点为根的唯一最大BSST，以其右子节点为根的唯一最大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