- 判断二叉树是否为平衡二叉树
1.1. 问题
平衡二叉树的性质：要么是一棵空树，要么任何一个节点的左右子树的高度差的绝对值不超过1,。
给定一个二叉树的头结点head，判断这棵二叉树是否为平衡二叉树。如果二叉树的节点数为N，要求时间复杂度为O(N)。
1.2. 思路
这道题比较简单，后序遍历，拿到两个子树的高度，然后进行判断。
1.3. 代码
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) > -1;
}
private int height(TreeNode node) {
if(null == node) {
return 0;
}
int leftHeight = height(node.left);
int rightHeight = height(node.right);
if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
Original: https://www.cnblogs.com/stepfortune/p/16261719.html
Author: 迈吉
Title: 二叉树——判断二叉树是否是平衡二叉树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/594674/
转载文章受原作者版权保护。转载请注明原作者出处！