IT评测·应用市场-qidao123.com技术社区

标题: 170.二叉树：均衡二叉树（力扣） [打印本页]

---

作者: 干翻全岛蛙蛙    时间: 2024-6-15 00:57
标题: 170.二叉树：均衡二叉树（力扣）

代码解决

  

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr, right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10. * };
11. */
13. class Solution {
14. public:
15.     // 递归计算二叉树的高度，同时检查是否平衡
16.     int height(TreeNode* root) {
17.         // 基本条件：如果节点为空，高度为0
18.         if (root == nullptr) return 0;
20.         // 递归计算左子树的高度
21.         int leftdeep = height(root->left);
22.         // 如果左子树不平衡，返回-1
23.         if (leftdeep == -1) return -1;
25.         // 递归计算右子树的高度
26.         int rightdeep = height(root->right);
27.         // 如果右子树不平衡，返回-1
28.         if (rightdeep == -1) return -1;
30.         // 如果左右子树高度差大于1，表示当前树不平衡，返回-1
31.         if (abs(leftdeep - rightdeep) > 1) return -1;
33.         // 否则返回当前树的高度，即左右子树高度的最大值加1
34.         return 1 + max(leftdeep, rightdeep);
35.     }
36.    
37.     // 判断二叉树是否平衡
38.     bool isBalanced(TreeNode* root) {
39.         // 调用height方法，如果返回值为-1，表示树不平衡，返回false
40.         return height(root) == -1 ? false : true;
41.     }
42. };

复制代码

• TreeNode 结构体定义：
  
  
  
  • val：节点的整数值。
    
  • left：指向左子节点的指针。
    
  • right：指向右子节点的指针。
    
  
  
• Solution 类：
  
  
  
  • 包含两个方法：height 和 isBalanced。
    
  
  
• height 方法：
  
  
  
  • 这是一个递归函数，用来盘算二叉树的高度，并查抄树是否均衡。
    
  • 根本条件：如果 root 为 nullptr，则返回高度 0。
    
  • 递归盘算左子树和右子树的高度：
    
    
    
    • 如果左子树的高度为 -1，表现左子树不均衡，直接返回 -1。
      
    • 如果右子树的高度为 -1，表现右子树不均衡，直接返回 -1。
      
    
    
  • 如果左右子树的高度差超过 1，表现当前树不均衡，返回 -1。
    
  • 否则，返回当前树的高度，即左右子树高度的最大值加 1。
    
  
  
• isBalanced 方法：
  
  
  
  • 这个方法调用 height 方法，如果返回值为 -1，表现树不均衡，返回 false。否则，返回 true，表现树是均衡的。
    
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4