二叉樹中最大的完整子樹

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); 
    } 
}