【每日算法】平衡二叉树
蓝字
描述
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
注:我们约定空树是平衡二叉树。
示例1
输入:
{1,2,3,4,5,6,7}
返回值:
true
题解
这是一篇针对初学者的题解,用两种方法解决。
知识点:树,递归
难度:一星
题解
方法一:自顶向下
判断一个数是否为平衡二叉树。平衡二叉树是左子树的高度与右子树的高度差的绝对值小于等于1,同样左子树是平衡二叉树,右子树为平衡二叉树。
根据定义,如果我们能够求出以每个结点为根的树的高度,然后再根据左右子树高度差绝对值小于等于1,,就可以判断以每个结点为根的树是否满足定义。
我们可以用hash<TreeNode*, int>
来存以每个结点的树的高度。
代码如下:
1 2 3 4 5 6 7 8 |
|
然后再用先序遍历:根节点、左子树、右子树
来判断以每个结点为根的树是否满足条件。
代码如下:
1 2 3 4 5 |
|
最后的代码为:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
时间复杂度:O(N)
空间复杂度:O(N)
方法二:自底向上
方法一是先求出以每个结点为根的树的高度,然后再判断,其实可以直接再求高度的同时,直接判断即可。
利用后序遍历:左子树、右子树、根节点
,可以先递归到叶子节点,然后在回溯的过程中来判断是否满足条件。
求树的高度的代码为:
1 2 3 4 5 6 |
|
然后对上述代码加以改造,如果不满足平衡二叉树的定义,则返回-1,并且如果左子树不满足条件了,直接返回-1,右子树也是如此,相当于剪枝,加速结束递归。
代码如下:
1 2 3 4 5 6 7 8 9 10 |
|
最后只需要判断depth(root)返回的是否为-1,如果是-1,则不是,否则,则是。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
时间复杂度:O(N)
空间复杂度:O(N)
import java.lang.*;
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null){
return true;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if(Math.abs(leftHeight - rightHeight) > 1){
return false;
}
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
public int getHeight(TreeNode root){
if(root == null){
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return 1 + (leftHeight > rightHeight ? leftHeight :rightHeight);
}
}
扫描关注
开启学习之路
BCS联盟