二叉树的特定算法 - 复杂度必须为 O(n)

Question

我必须写一个程序来验证二叉树是否满足这个属性:

for each node of the tree, the height of its subtrees (right and left) must differ for max 1.

不好：

好:

我构建的算法具有 O((n^2)log(n)) 的复杂性。

感谢您的帮助！

bool check(node* root){
    if(!root->right && !root->left){
        return;
    }

    int h;
    int n_node;
    int hRight, hLeft;

    h = height(root);
    hRight = height_right(root);
    hLeft = height_left(root);

    n_node = pow(2, heihgt+1)-1;

    if((hRight > n_node/2 && hLeft <= n_node/4) ||  (hLeft > n_node/2 && hRight <= n_node/4)
       return true;
}

我知道不好看但是是一种尝试。请注意，此算法的复杂度为 O(nlog(n))，因为它仅适用于第一个节点（根）。所以我必须把它放在另一个块中才能滚动节点。

Answer 1

当平衡树的定义就在你面前时，你还不清楚为什么要计算节点数——根据高度，而不是节点数。

棘手的部分是，如果您分别计算深度和检查平衡，您将以过于复杂的方式结束（我认为是 O(n^2)）。

因此您需要一个辅助函数，在遍历树时计算两者。
这是一个非常简单的解决方案：

// Returns whether 'root' is a balanced tree.
// Also stores the tree's height in *height.
bool balanced_height(node* root, int* height)
{
   // The trivial base case – an empty tree is balanced and has height 0.
   if (root == nullptr)
   {
      *height = 0;
      return true;
   }

   // Information gathering using recursion:
   // Find out whether the subtrees are balanced, and get their heights.
   int leftheight = 0;
   int rightheight = 0;
   bool leftbalance = balanced_height(root->left, &leftheight);
   bool rightbalance = balanced_height(root->right, &rightheight);

   // Now that we know the heights of the subtrees,  we can store the height of this tree.
   *height = max(leftheight, rightheight) + 1;

   // Finally, a translation into C++ of the definition:
   // A tree is balanced if and only if
   //   - the subtrees are balanced, and
   //   - the heights of the subtrees differ by at most one.
   return leftbalance && rightbalance && abs(leftheight - rightheight) <= 1;
}

bool balanced(node* root)
{
     int height = 0;
     return balanced_height(root, &height);
}

在不平衡的情况下，如果第一个子树不平衡，则不遍历第二个子树，可以使它稍微快一些（但具有相同的复杂性），因为在那种情况下我们不会将高度用于任何事情。
该优化留作练习。

二叉树的特定算法 - 复杂度必须为 O(n)

Particular Algorithm For Binary Tree - Complexity must be O(n)

c++

algorithm

binary-tree