二叉树中最大的完整子树

Question

我将一棵完整的子树定义为一棵树，所有级别都已满，最后一级左对齐，即所有节点都尽可能地离开，我想在树中找到最大的子树这是完整的。

一种方法是对每个节点以root身份执行概述为here的方法，这将需要O（n^2）个时间。

有没有更好的方法？

Answer 1

定义树节点的等级，如果此节点是root，则为最大完整子树的高度。 如果此节点是root，则将节点的宽度定义为max complete subtree的最后一级中的节点数。 因此对于树中的每个节点，我们有两个数字(r, w)。和w <= 2^r。

如果节点有零个或只有一个孩子，那么节点有(r, w) = (1, 1)。

如果节点有两个孩子(r1, w1)和(r2, w2)，我们有几种情况：

1. r1 > r2当节点有(r2 + 1, 2^r2 + w2)
2. r1 == r2和w1 == 2^r1当节点有(r1 + 1, w1 + w2)
3. r1 == r2和w1 < 2^r1当节点会有(r1 + 1, w1)例如：

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

最大完整子树是

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

r1 < r2和w1 == 2^r1当节点将具有(r1 + 1, 2 * w1)实施例：

     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 

r1 < r2和w1 < 2^r1当节点将具有(r1 + 1, w1)

实施例：

     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

我在编写元素编程访谈的变体时遇到了这篇文章。我想分享我的想法和代码。

任何意见都欢迎。

我使用递归来解决这个问题。 max用于存储有史以来发生的最大尺寸（我使用的数组，因为java是按值计算的）。 返回值信息包含有关树 传入的树是否为完整树的信息。完成时只返回树大小，否则返回（-1，false）。 如果一个子树T'不完整，它的大小永远不会被选中来组成一个更大的完整树。所有T的子树的大小将始终以最大值记录，所以我们绝不会错过任何值。

下面是它如何工作的

• 基本情况：根== null或根叶
• 递归处理左孩子和右孩子。 leftInfo和rightInfo - 基于左/右孩子的返回值

• 处理当前的树。

• 如果两者都不是完整的，树是不完整的，不需要更新 最大。如果其中任何一个都完成，树不完整，请将最大更新为 左右较大的大小。如果两者都完成，树 可能会完成。首先检查左边是否完美，并且 正确满足高度要求。如果是，则返回（true， newSize）。否则，树不完整，更新最大值为 更大的左右值。

下面是我code.It应及时O（n）和空间O（h），其中h是树的高度。（如果是平衡的，否则，最坏的情况将是为O（n ））。

public class Solution { 

    public static void main(String[] args){ 
     TreeNode[] trees = new TreeNode[10]; 
     for(int i = 0; i < 10; i++){ 
      trees[i].val = i; 
     } 
    } 

    public int largestCompleteTree(TreeNode root){ 
     int[] max = new int[1]; 
     helper(root, max); 
     return max[0]; 
    } 

    private Info helper(TreeNode root, int[] max){ 
     //Base case: 
     if(root == null){ 
      return new Info(0, true); 
     } 

     if(root.left == null && root.right == null){ 
      max[0] = Math.max(max[0], 1); 
      return new Info(1, true); 
     } 

     //Recursion 
     Info leftInfo = helper(root.left, max); 
     Info rightInfo = helper(root.right, max); 

     //Process based on left subtree and right subtree. 
     //Neither is complete. 
     if(!leftInfo.isComplete && !rightInfo.isComplete){ 
      //Do not need to update the max value. 
      return new Info(-1, false); 
     } 
     //One of the subtree is complete, the current tree is not complete 
     else if(!leftInfo.isComplete || !rightInfo.isComplete){ 
      if(leftInfo.isComplete){ 
       max[0] = Math.max(max[0], leftInfo.size); 
       return new Info(-1, false);//the value has been recorded 
      }else{ 
       max[0] = Math.max(max[0], rightInfo.size); 
       return new Info(-1, false); 
      } 
     } 
     //Both subtrees are complete,   
     else{ 
      int size = 0; 
      if(((rightInfo.size & (rightInfo.size + 1)) == 0 && 
       leftInfo.size >= rightInfo.size && 
       leftInfo.size <= rightInfo.size*2 + 1)|| 
       ((leftInfo.size & (leftInfo.size + 1)) == 0 && 
         rightInfo.size >= (leftInfo.size - 1)/2 && 
         rightInfo.size <= leftInfo.size)) 
       { 
        size = leftInfo.size + rightInfo.size + 1; 
        max[0] = Math.max(max[0], size); 
        return new Info(size, true); 
       } 
      else{ //find the subtree with the greater size 
       size = leftInfo.size > rightInfo.size ? leftInfo.size : rightInfo.size; 
       max[0] = Math.max(max[0], size); 
       return new Info(0, false); 
      } 
     } 
    } 
    class Info { 
     boolean isComplete; 
     int size; 

     public Info(int size, boolean isComplete){ 
      this.isComplete = isComplete; 
      this.size = size; 
     } 
    } 
} 

Answer 3

会见了著作“编程采访的元素”这一任务，它似乎是我发现了一个很简单的解决方案，仍然不知道这是否是正确的，但测试它的一对夫妇的情况下，它的工作：

private struct str 
     { 
      public bool isComplete; 
      public int height, size; 
      public str(bool isComplete, int height, int size) 
      { 
       this.isComplete = isComplete; 
       this.height = height; 
       this.size = size; 
      } 
     } 

     public int SizeOfLargestComplete() 
     { 
      return SizeOfLargestComplete(root).size; 
     } 

     private str SizeOfLargestComplete(Node n) 
     { 
      if (n == null) 
       return new str(true, -1, 0); 
      str l = SizeOfLargestComplete(n.left); 
      str r = SizeOfLargestComplete(n.right); 

      if (!l.isComplete || !r.isComplete) 
       return new str(false, 0, Math.Max(l.size, r.size)); 

      int numberOfLeftTreeLeafes; 
      if (l.height == -1) 
       numberOfLeftTreeLeafes = 0; 
      else 
       numberOfLeftTreeLeafes = l.size - ((1 << l.height) - 1); 

      bool leftTreeIsPerfect = (1 << (l.height + 1)) - 1 - l.size == 0; 

      //if left subtree is perfect, right subtree can have leaves on last level 
      if (leftTreeIsPerfect) 
       if (l.size - r.size >= 0 && l.size - r.size <= numberOfLeftTreeLeafes) 
        return new str(true, l.height + 1, l.size + r.size + 1); 
       else 
        return new str(false, 0, Math.Max(l.size, r.size)); 
      //if left subtree is not perfect, right subtree can't have leaves on last level 
      //so size of right subtree must be the same as left without leaves 
      else 
       if (r.size == l.size - numberOfLeftTreeLeafes) 
       return new str(true, l.height + 1, l.size + r.size + 1); 
      else 
       return new str(false, 0, Math.Max(l.size, r.size)); 

     } 

Answer 4

由于没有上述一个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}; 
} 

Answer 5

这是我在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 6

我到达一个类似于米哈伊尔的解决方案的解决方案（在我阅读EPI书籍时遇到）。我已经测试了一棵完整的树，一棵完美的树，一棵完整的树以及带有完整子树的树，但没有穷尽。

/** 
* Returns the largest complete subtree of a binary tree given by the input node 
* 
* @param root the root of the tree 
*/ 
public int getLargestCompleteSubtree(INode<TKeyType, TValueType> root) { 
    max = 0; 
    calculateLargestCompleteSubtree(root); 

    return max; 
} 

/** 
* Returns the largest complete subtree of a binary tree given by the input node 
* 
* @param root the root of the tree 
*/ 
public TreeInfo<TKeyType, TValueType> calculateLargestCompleteSubtree(INode<TKeyType, TValueType> root) { 
    int size = 0; 

    // a complete subtree must have the following attributes 
    // 1. All leaves must be within 1 of each other. 
    // 2. All leaves must be as far left as possible, i.e, L(child).count() > R(child).count() 
    // 3. A complete subtree may have only one node (L child) or two nodes (L, R). 

    if (root == null) 
    { 
     return new TreeInfo<>(true, 0); 
    } 
    else if (!root.hasLeftChild() && !root.hasRightChild()) 
    { 
     return new TreeInfo<>(true, 1); 
    } 

    // have children 
    TreeInfo<TKeyType, TValueType> leftInfo = calculateLargestCompleteSubtree(root.getLeft()); 
    TreeInfo<TKeyType, TValueType> rightInfo = calculateLargestCompleteSubtree(root.getRight()); 

    // case 1: not a complete tree. 
    if (!leftInfo.isComplete || !rightInfo.isComplete) 
    { 
     // Only one subtree is complete. Set it as the max and return false. 
     if(leftInfo.isComplete) { 
      max = Math.max(max, leftInfo.size); 
     } 
     else if(rightInfo.isComplete) 
     { 
      max = Math.max(max, rightInfo.size); 
     } 

     return new TreeInfo<>(false, -1); 
    } 

    // case 2: both subtrees complete 
    int delta = Math.abs(leftInfo.size - rightInfo.size); 
    if (delta <= 1) 
    { 
     // both are complete but R could be 1 greater...use L tree. 
     size = leftInfo.size + 1; 
     max = Math.max(max, size); 
     return new TreeInfo<>(true, size); 
    } 
    else 
    { 
     // limit to size of R + 1 if L - R > 1, otherwise L 
     if(leftInfo.size > rightInfo.size) 
     { 
      max = Math.max(max, leftInfo.size); 
      size = rightInfo.size + 1; 
     } 
     else 
     { 
      max = Math.max(max, rightInfo.size); 
      size = leftInfo.size; 
     } 

     return new TreeInfo<>(true, size + 1); 
    } 
}