LeetCode-110. Balanced Binary Tree

LeetCode-110. 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.

Example 1:

Given the following tree ​​[3,9,20,null,null,15,7]​​:

3 / \ 9 20 / \ 15 7

Return true.Example 2:

Given the following tree ​​[1,2,2,3,3,null,null,4,4]​​:

1 / \ 2 2 / \ 3 3 / \ 4 4

Return false.

题解：

class Solution {public: void postOrder(TreeNode* &root, bool &res) { if (res == false || root == NULL) { return; } postOrder(root->left, res); postOrder(root->right, res); int dep = 0; if (root->left == NULL && root->right == NULL) { root->val = 1; } else if (root->left == NULL && root->right != NULL) { root->val = 1 + root->right->val; dep = root->right->val; } else if (root->left != NULL && root->right == NULL) { root->val = 1 + root->left->val; dep = root->left->val; } else if (root->left != NULL && root->right != NULL) { root->val = 1 + max(root->right->val, root->left->val); dep = abs(root->left->val - root->right->val); } if (dep > 1) { res = false; } } bool isBalanced(TreeNode* root) { bool res = true; postOrder(root, res); return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。