題目描述
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.
題目思路
- 劍指offer 273
代碼 C++
- 思路一牡辽、需要重復遍歷節(jié)點多次的解法
如果每個節(jié)點的左右子樹的深度相差都不超過1僧界，那么按照定義它就是一顆平衡二叉樹
/**
* Definition for a binary tree node.
* 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;
}
int depth_left = Depth(root->left);
int depth_right = Depth(root->right);
int tt = depth_left - depth_right;
if(tt < -1 || tt > 1){
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
int Depth(TreeNode* root){
if(root == NULL){
return 0;
}
int depth_left = Depth(root->left);
int depth_right = Depth(root->right);
return (depth_left > depth_right) ? (depth_left+1) : (depth_right+1);
}
};
- 思路二棒坏、每個節(jié)點只遍歷一次的解法，正是面試官喜歡的
在下面代碼中潜叛，我們用后序遍歷的方式遍歷整顆二叉樹秽褒。
在遍歷某節(jié)點的左右子節(jié)點之后，我們可以根據(jù)它的左右子節(jié)點的深度判斷它是不是平衡的威兜，并得到當前結點的深度销斟。當最后遍歷到樹的根節(jié)點的時候，也就判斷了整顆二叉樹是不是平衡二叉樹椒舵。
class Solution {
public:
bool isBalanced(TreeNode* root) {
int depth = 0;
return core(root, &depth);
}
bool core(TreeNode* root, int* depth){
if(root == NULL){
*depth = 0;
return true;
}
int left, right;
if(core(root->left, &left) && core(root->right, &right)){
int diff = left - right;
if(diff >= -1 && diff <= 1){
*depth = (left > right) ? left+1 : right+1;
return true;
}
}
return false;
}
};
