首页 > 代码库 > [leetcode] Balanced Binary Tree

[leetcode] Balanced Binary Tree

2024-07-02 03:49:45   231人阅读

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。depth为该节点的深度初始化为0。

代码如下：

 1 /** 
 2  * Definition for binary tree 
 3  * struct TreeNode { 
 4  *     int val; 
 5  *     TreeNode *left; 
 6  *     TreeNode *right; 
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 8  * }; 
 9  */ 
10 class Solution {  
11     public:  
12         bool isBalanced(TreeNode *root) {  
13             // Note: The Solution object is instantiated only once and is reused by each test case.  
14             int depth = 0;  
15             return isbalance(root, depth);  
16         }  
17         bool isbalance(TreeNode *root, int &depth)  
18         {  
19             if(root == NULL)  
20             {  
21                 depth = 0;  
22                 return true;  
23             }  
24             int ld,rd;  
25             if( isbalance(root->left,ld) && isbalance(root->right,rd))  
26             {  
27                 if( abs(ld - rd) > 1)  
28                 {  
29                     return false;  
30                 }  
31                 depth = ld > rd ? ld + 1 : rd + 1;  
32                 return true;  
33             }
34             else return false;
35         }  
36 };

 


联系
我们