LeetCode:110_Balanced Binary Tree | 平衡二叉树 | Easy

要求:判断一棵树是否是平衡二叉树

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 struct TreeNode {
 2     int            val;
 3     TreeNode    *left;
 4     TreeNode    *right;
 5     TreeNode(int x): val(x),left(NULL), right(NULL) {}
 6 };
 7 
 8 int maxTreeDepth(TreeNode *root) //先求树的深度
 9 {
10     if (NULL == root)
11         return 0;
12     int lval = maxTreeDepth(root->left);
13     int rval = maxTreeDepth(root->right);
14     return 1 + (lval > rval ? lval:rval);
15 }
16 bool isBalanced(TreeNode *root)//根据树的深度再来判断是否是平衡树
17 {
18     if(NULL == root)
19         return true;
20     int diff = maxTreeDepth(root->left) - maxTreeDepth(root->right);
21     if (diff < -1 || diff > 1)
22         return false;
23     return isBalanced(root->left) && isBalanced(root->right);
24 }

 

上一篇:让你上瘾的网易云音乐推荐算法,用Word2vec就可以实现


下一篇:Spring Boot Serverless 实战系列“架构篇” | 光速入门函数计算