二叉树（七）：二叉树的高度与平衡二叉树

一、二叉树的深度与高度

1、二叉树的深度

对于二叉树中的某个节点，其深度是从根节点到该节点的最长简单路径所包含的节点个数，是从上面向下面数的。因此访问某个节点的深度要使用先序遍历

2、二叉树的高度

对于二叉树中的某个节点其高度是从叶子节点到该节点的最长简单路径包含的节点个数，是从下面向上面数的。因此访问某个节点的高度需要使用后续遍历

3、二叉树的深度与高度辨析

每层节点的深度和高度如图所示：

4、二叉树的深度与高度的联系

一个二叉树根节点的高度就是这个二叉树的最大深度

二、二叉树的高度

1、递归法

递归三要素：

1. 递归返回值和参数：返回值为当前节点的高度，参数为当前节点
2. 递归单层逻辑：当前节点高度 = 1 + max（左子树高度，右子树高度）
3. 递归终止条件：当前节点为空，返回高度为0，结束递归

2、递归法代码

class Solution {
public:
	//递归参数及返回值
    int height(TreeNode* root) {
    
    	//递归终止条件
        if(root == nullptr) return 0;
        
        //单层递归逻辑
        int leftheight = height(root->left);
        int rightheight = height(root->right);
        return 1 + max(leftheight , rightheight );
    }
};

三、平衡二叉树

110.平衡二叉树

平衡二叉树定义：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

1、递归法解题思路

给定一个节点，分别求取其左右孩子为根节点的子树的高度，相比较是否相差1。而一旦有子树不为平衡二叉树的时候，该结果需要递归传递，最后输出整棵树不是平衡二叉树

1. 递归返回值和参数：递归返回值为当前节点为根节点的二叉树高度，当前二叉树是否为平衡二叉树，参数为当前节点
2. 单层递归逻辑：当前节点二叉树高度 = 1 + max(左子树高度，右子树高度)；当前节点是否为平衡二叉树 = 左子树高度与右子树高度差值是否大于1
3. 递归结束条件：当前节点为空，二叉树高度为0，当前节点时平衡二叉树

优化：我们可以利用树木的高度为-1来表示子树不是平衡二叉树，从而减少返回参数

2、递归法解题代码

class Solution {
public:
	//递归返回值和参数
    int treeheight(TreeNode* root){
    
    	//递归终止条件
        if(root == nullptr) return 0;
        
		//单层递归逻辑
		//获取左右树高度，如果左右树已经存在不平衡，递归终止，直接返回-1
        int leftheight = treeheight(root->left);
        if(leftheight == -1) return -1;
        int rightheight = treeheight(root->right);
        if(rightheight == -1) return -1;
		//如果左右树不存在不平衡，根据左右树高度计算当前节点是否平衡，以返回当前高度或-1
        if(abs(leftheight - rightheight) > 1) return -1;
        return 1 + max(leftheight, rightheight);
    }
    bool isBalanced(TreeNode* root) {
    	//调用递归判定是否为平衡二叉树
        if(treeheight(root) != -1) return true;
        return false;
    }
};