如何在给定的二叉树中找到最大大小为 K 的所有有根子树？

Question

如题。如何高效地生成与原始二叉树同根的所有子树？

Answer 1

这与生成所有大小为 k 的未标记二叉树非常相似，其算法如下所示：

trees(k):
    if k is zero:
        yield the null tree
    else:
        for i from 0 to k-1:
            for l in trees(i):
                for r in trees(k-i):
                    yield the tree whose root has left subtree l
                        and right subtree r

您应该能够在您最喜欢的编程语言中找到它的具体实现。

为了解决这个问题，我们修改这段代码，在递归的同时分解给定的树。

subtrees(T, k):
    if k is zero:
        yield the null tree
    else if T is not null:
        let L be the left subtree of T's root
        let R be the right subtree of T's root
        for i from 0 to k-1:
            for l in subtrees(L, i):
                for r in subtrees(R, k-i):
                    yield the tree whose root has the same value as T's,
                        with left subtree l and right subtree r

如何在给定的二叉树中找到最大大小为 K 的所有有根子树？

How to find all rooted subtrees of at most size K in a given binary tree?

algorithm

binary-tree