LeetCode110 - Balanced Binary Tree

浅浅的花香味﹌ 2022-08-07 08:55 139阅读 0赞

[Q]

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.

[C++]

/**
* 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) {
if (root == NULL) return true; 

  1.     int leftDepth = treeDepth(root -> left);  
  2.     int rightDepth = treeDepth(root -> right);  
  3.     if (leftDepth - rightDepth >= -1 && leftDepth - rightDepth <= 1) \{  
  4.         return isBalanced(root -> left) && isBalanced(root -> right);  
  5.     \}  
  6.     else \{  
  7.         return false;  
  8.     \}  
  9. \}  
  11. int treeDepth (TreeNode \*root) \{  
  12.     if (root == NULL) return 0;  
  13.     int left = treeDepth(root -> left);  
  14.     int right = treeDepth(root -> right);  
  15.     return left > right ? left + 1 : right + 1;  
  16. \}

};

发表评论

表情：
评论列表 （有 0 条评论，139人围观）

还没有评论，来说两句吧...

相关阅读