C++ 程序检查树是否为平衡树

假设我们有一个二叉树，我们需要检查其高度是否平衡。我们知道，对于一个高度平衡的树，树中每个节点的左子树高度和右子树高度的绝对差为 0 或 1。

所以，如果输入如下所示：

则输出为 True

为了解决这个问题，我们将遵循以下步骤：

• 定义一个函数 dfs()，它将接收节点作为参数。

• 如果节点为空，则：

  • 返回 0

• l := 1 + dfs(节点的左子节点)

• r := 1 + dfs(节点的右子节点)

• 如果 |l - r| > 1，则：

  • ret := false

• 返回 l 和 r 中的最大值

• 在主方法中执行以下操作：

• ret := true

• dfs(根节点)

• 返回 ret

让我们看看下面的实现来更好地理解：

示例

 在线演示

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
   public:
   bool ret;
   int dfs(TreeNode* node){
      if(!node)
         return 0;
      int l = 1 + dfs(node->left);
      int r = 1 + dfs(node->right);
      if(abs(l - r) > 1)
         ret = false;
      return max(l, r);
   }
   bool isBalanced(TreeNode* root) {
      ret = true;
      dfs(root);
      return ret;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(25);
   root->left = new TreeNode(19);
   root->right = new TreeNode(4);
   root->left->left = new TreeNode(9);
   root->left->right = new TreeNode(7);
   cout << (ob.isBalanced(root));
}

输入

TreeNode *root = new TreeNode(25);
root->left = new TreeNode(19);
root->right = new TreeNode(4);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(7);

输出

1

Arnab Chakraborty

更新于: 2020年10月8日

501 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习