算法力扣刷题记录 四十五【110.平衡二叉树】

前言

二叉树篇继续
记录 四十五【110.平衡二叉树】

---

一、题目阅读

给定一个二叉树，判断它是否是 平衡二叉树。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-10^4 <= Node.val <= 10^4

---

二、尝试实现

思路

平衡二叉树概念：左右子树高度差不超过1。
至于搜索树，需要左节点<中节点<右节点（本题和这个数值无关）。

1. 如果获取左子树高度；再获取右子树高度；比较不超过1，return true；否则，return false.

2. 但是这样写完之后，发现只判断了根节点，没有遍历整个树。如果某个子树不平衡，那么整个树也不平衡。
   

3. 所以走一个层序遍历，判断每个子树都是平衡的，那么整个树平衡。

代码实现

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int getheight(TreeNode* cur){if(!cur) return 0;int left = getheight(cur->left);int right = getheight(cur->right);return max(left,right)+1;}bool subbanlance(TreeNode* cur){int leftheight = getheight(cur->left);int rightheight = getheight(cur->right);if(abs(leftheight-rightheight) <= 1){return true;}else{return false;}}bool isBalanced(TreeNode* root) {if(!root) return true;//走一个层序遍历queue<TreeNode*> que;que.push(root);while(!que.empty()){TreeNode* cur = que.front();que.pop();if(!subbanlance(cur)){//如果一个子树返回false，说明整个树不是平衡return false;}//如果这个子树平衡，继续if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}return true;}};

---

三、参考学习

参考思路链接

学习内容

1. 平衡二叉树概念：任何一个节点的左右子树高度差不超过1.
2. 用后序遍历：左右中。
3. 递归逻辑：

• 判断每个节点的左子树高度和右子树高度差>1，说明不平衡，return -1。这个节点的高度不再返回。
• 如果该节点的左子树高度和右子树高度差<=1，说明平衡，return max(左子树高度，右子树高度)+1。返回这个节点的高度值。
• 继续回归。

4. 递归代码实现

   /*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
   class Solution {
   public:int getheight(TreeNode* cur){if(!cur) return 0;//终止条件int leftheight = getheight(cur->left);if(leftheight == -1) return -1;//已经不平衡int rightheight = getheight(cur->right);if(rightheight == -1) return -1;if(abs(leftheight-rightheight) >1){return -1;//不平衡}else{return max(leftheight,rightheight)+1;}}bool isBalanced(TreeNode* root) {return getheight(root) == -1 ? false:true;}
   };
   

5. 迭代法：就是【二、尝试实现】中的代码。用的是层序遍历每一个节点。对比参考
   

---

总结

判断平衡二叉树：每个节点的左右子树高度差不超过1.

• 递归：用后序遍历。如果当前节点左右子树高度差不超过1，向上一层返回当前节点的高度；如果不平衡，向上一层return -1.
• 迭代：先实现一个固定节点左右子树高度差的判断；再在主函数中用层序遍历，判断每个节点是不是平衡。

（欢迎指正，转载标明出处）