LeetCode 110.平衡二叉树

题目描述

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

示例 1：

示例 2：

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

示例 3：

输入：root = []
输出：true

提示：

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

思路

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

递归三部曲：

确定递归函数的参数和返回值。参数：当前传入节点。返回值：以当前传入节点为根节点的树的高度。
确定终止条件。递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0。
确定单层递归的逻辑。分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。-1是标记，表示已经不是平衡二叉树了。

代码

C++版：

/*** 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:// 递归法，后序遍历// 返回-1表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度int getHeight(TreeNode* node){if(node==NULL) return 0; // 叶子结点高度为0// 如果子树不是平衡二叉树，那么整棵树就不是平衡二叉树int leftHeight=getHeight(node->left); // 左，求左子树高度if(leftHeight==-1) return -1; int rightHeight=getHeight(node->right); // 右，求右子树高度if(rightHeight==-1) return -1;// 中，左右子树都是平衡二叉树int result=0;if(abs(leftHeight-rightHeight)>1){return -1;}else{result=max(leftHeight,rightHeight)+1;}return result; // 返回高度  }bool isBalanced(TreeNode* root) {return getHeight(root)==-1? false:true;}
};

Python版：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:# 递归法，后序遍历def getHeight(self,node: Optional[TreeNode]) -> int:if not node:return 0# 左leftHeight = self.getHeight(node.left)if leftHeight==-1 :return -1# 右rightHeight = self.getHeight(node.right)if rightHeight==-1 :return -1# 中    if abs(leftHeight-rightHeight)>1 :return -1else :return max(leftHeight,rightHeight)+1def isBalanced(self, root: Optional[TreeNode]) -> bool:if self.getHeight(root) ==-1 :return Falseelse :return True