二叉树中最大的完整子树

Question

我将完整子树定义为所有级别都已满且最后一个级别左对齐的树，即所有节点都尽可能左对齐，我希望找到树中最大的完整子树。

一种方法是对每个节点作为根执行这里概述的方法，这将花费O（n^2）时间。

有更好的方法吗？

Answer 1

定义树节点的秩，如果此节点是根节点，则将其定义为最大完整子树的高度。如果节点是根节点，则将节点宽度定义为“最大完整子树”最后一级中的节点数。所以对于树中的每个节点，我们有两个编号（r，w）。和w

若节点有零个子节点或只有一个子节点，则节点有（r，w）=（1，1）。

如果节点有两个子节点（r1，w1）和（r2，w2），我们有几种情况：

1. r1

         root     
         ....
    /  \     /   \
   l    l    r    r
  /\   /    /\    /
  l l  l    r r  r

最大完全子树是

          m     
         ....
    /  \     /   \
   m    m    m    m
  /\   /    /\    /
  m m  m    r r  r

         root     
         ....
    /  \      /   \
   l    l     r    r
  /\   / \    /\    /\
  l l  l  l   r r  r  r
             /
            r

最大完全子树是

          m     
         ....
    /  \      /   \
   m    m     m    m
  /\   / \    /\    /\
 m  m  m  m   m m  m  m
             /
            r

例子：

         root     
         ....
    /  \      /   \
   l    l     r    r
  /\   /      /\    /\
  l l  l      r r  r  r
             /
            r

最大完全子树是

          m     
         ....
    /  \      /   \
   m    m     m    m
  /\   /     /\    /\
 m  m  m     r r  r  r
            /
            r

基于此规则，您可以使用递归为每个节点计算（r，w）。这将需要O（n）。当您在这些节点中找到具有最大秩r的节点时，请查找具有最大秩w的节点，并且该节点应该是一个解决方案。

Answer 2

这是我的Python解决方案。它正在处理我提出的案子。返回值的含义如下：[x，y，z]

>

x=此节点之前最大完整子树的大小

y=子树的高度

z:0-完整子树，1-此子树中只有一个节点具有左子树，2-不是完整子树

def largest_complete_tree(root):

    result = traverse_complete(root)
    print('largest complete subtree: {}'.format(result[0]))

def traverse_complete(root):
    if root:
        left = traverse_complete(root.left)
        right = traverse_complete(root.right)
        max_complete = max(left[0], right[0])
        max_height = max(left[1], right[1])
        left_child_only = 1 if (left[2] == 1 and right[0] == 0) or (left[0] == 1 and right[0] == 0) else 0

        # 5 conditions need to pass before left and right can be joined by this node
        # to create a complete subtree.
        if left[0] < right[0]:
            return [max_complete, 0, 2]
        if left[2] == 2 or right[2] == 2:
            return [max_complete, 0, 2]
        if abs(left[1]-right[1]) > 1:
            return [max_complete, 0, 2]
        if (left[2] == 1 and right[2] == 1) or (left[2] == 0 and right[2] == 1):
            return [max_complete, 0, 2]
        if left[0] == right[0] and left[0] != 2**left[0] - 1:
            return [max_complete, 0, 2]
        return [left[0] + right[0] + 1, max_height + 1, left_child_only]
    else:
        return [0,0,0]

Answer 3

因为上面没有C解决方案，所以我添加了我的解决方案。让我知道，如果你觉得有什么不正确的或任何可以改进。

struct CompleteStatusWithHeight {
 bool isComplete;
 int height;
};

int FindLargestCompletetSubTreeSize(const unique_ptr<BinaryTreeNode<int>>& tree)
{
  return CheckComplete(tree).height;
}

CompleteStatusWithHeight CheckComplete(const unique_ptr<BinaryTreeNode<int>>& tree)
{
if (tree == nullptr) {
       return {true, -1};  // Base case.
}

auto left_result = CheckComplete(tree->left);
if (!left_result.isComplete) {
  return {false, 0};  // Left subtree is not balanced.
}
auto right_result = CheckComplete(tree->right);
if (!right_result.isComplete) {
  return {false, 0};  // Right subtree is not balanced.
}

bool is_balanced = abs(left_result.height - right_result.height) == 0;
bool is_left_aligned = (left_result.height - right_result.height) == 1;
bool is_leaf =  left_result.height  == -1 && right_result.height ==-1;
bool is_complete = is_balanced || is_left_aligned || is_leaf;

int height = max(left_result.height, right_result.height) + 1;
return {is_complete, height};
}