LeetCode 题解（20）: Balanced Binary Tree

本文主要是介绍LeetCode 题解（20）: Balanced Binary Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

题解：

后序遍历树，若任一子树不平衡，则直接递归返回至根节点，无需再判断其它子树，用-1表示不平衡。若当前节点的左右子树平衡，则计算当前节点的深度，并当做返回值返回。

/*** Definition for binary tree* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isBalanced(TreeNode *root) {int result = isBalancedRecursion(root);if(result == -1)return false;elsereturn true;}int isBalancedRecursion(TreeNode *root){if(root == NULL)return 0;if(isBalancedRecursion(root->left) == -1)return -1;if(isBalancedRecursion(root->right) == -1)return -1;int leftHeight = isBalancedRecursion(root->left);int rightHeight = isBalancedRecursion(root->right);if(abs(leftHeight-rightHeight) > 1)return -1;elsereturn leftHeight < rightHeight ? rightHeight + 1 : leftHeight + 1;}
};

这篇关于LeetCode 题解（20）: Balanced Binary Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---