对于给定的二叉树,找到最大的子树也是二叉搜索树?
Example:
Input:
10
/ \
50 150
/ \ / \
25 75 200 20
/ \ / \ / \ / \
15 35 65 30 120 135 155 250
Output:
50
/ \
25 75
/ \ /
15 35 65
该答案之前包含基于链接/切割树的 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
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)