Java教程

算法-二叉树：平衡二叉树

本文主要是介绍算法-二叉树：平衡二叉树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

算法-二叉树：平衡二叉树

判断一棵树是不是平衡二叉树。平衡二叉树：每一个节点的左子树和右子树的高度差的绝对值不超过1。

思路解析：求二叉树的高度，只能从下到上去查找，所以需要后序遍历。和求深度不同。

//方法一：递归
int height(TreeNode* root){
    if(root == NULL) return 0;
    int leftHeight = height(root->left);
    if(-1 == leftHeight) return -1;
    int rightHeight = height(root->right);
    if(-1 == rightHeight) return -1;
    if(abs(leftHeight-rightHeight) > 1) return -1; //如果高度返回-1，表明这棵树不是平衡二叉树
    return 1+max(leftHeight,rightHeight);
}

方法二：迭代，采用后序遍历的统一迭代法，用迭代方法实现回溯算法效率很低，在此不做过多说明。

这篇关于算法-二叉树：平衡二叉树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航