LeetCode刷题记录：110. 平衡二叉树

英雄爱吃土豆片

发布于 2020-10-29 11:02:21

2370

发布于 2020-10-29 11:02:21

110. 平衡二叉树

解题思路： 使用递归遍历二叉树，求出每个二叉树节点的高度并进行判断。递归时若二叉树节点没有子节点，返回 0；若二叉树左右节点的高度差的绝对值大于 1 ，说明树已经不满足平衡树的条件，返回 -1 ；否则返回当前节点的最高高度（即左右节点高度中的最大值 + 1）。

通关代码：

class Solution {
public:
	int height(TreeNode* root) {
		if (root == NULL) {
			return 0;
		}
		
		int left = height(root->left);
		int right = height(root->right);
		
		if (left == -1 || right == -1 || abs(left - right) > 1) {
			return -1;
		}
		
		return max(left, right) + 1;
	}
	
    bool isBalanced(TreeNode* root) {
        if (height(root) == -1) {
        	return false;
		}
		
		return true;
    }
};

通关截图：