剑指offer 39.知识迁移能力平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

解题思路

/后续遍历二叉树，遍历过程中求子树高度，判断是否平衡

代码如下

public boolean IsBalanced_Solution(TreeNode root) {
                return getDepth(root) != -1;
            }
             
            private int getDepth(TreeNode root) {
                if (root == null) return 0;
                int left = getDepth(root.left);
                if (left == -1) return -1;
                int right = getDepth(root.right);
                if (right == -1) return -1;
                return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
            }

平衡二叉树简介

定义

平衡二叉树也叫自平衡二叉搜索树（Self-Balancing Binary Search Tree），所以其本质也是一颗二叉搜索树，不过为了限制左右子树的高度差，避免出现倾斜树等偏向于线性结构演化的情况，所以对二叉搜索树中每个节点的左右子树作了限制，左右子树的高度差称之为平衡因子，树中每个节点的平衡因子绝对值不大于 $1$ ，此时二叉搜索树称之为平衡二叉树。

自平衡是指，在对平衡二叉树执行插入或删除节点操作后，可能会导致树中某个节点的平衡因子绝对值超过 $1$ ，即平衡二叉树变得“不平衡”，为了恢复该节点左右子树的平衡，此时需要对节点执行旋转操作。

情景分析

在执行插入或删除节点操作后，平衡因子绝对值变为大于 $1$ 的情况，即左右子树的高度差为 $-2$ 或 $2$ 的情况，可以归纳为如下四种：

左左情况(LL)

$LL$ 情况是指根节点的平衡因子为 $2$ ，根节点的左子节点平衡因子为 $0$ 或 $1$ 。

LL_1

如图 LL_1 所示，当节点 $C$ 的子节点被删除，或者节点 $D$ 插入子节点 $F$ 时，根节点 $A$ 的平衡因子变为 $2$ ， $A$ 的左子节点 $B$ 的平衡因子为 $1$ 。

LL_2

或者如图 LL_2 所示，当节点 $C$ 的子节点被删除，根节点 $A$ 的平衡因子变为 $2$ ， $A$ 的左子节点 $B$ 的平衡因子为 $0$ 。

当根节点的左子树高度比右子树的高度大 $2$ ，因为平衡二叉树是一种有序结构，节点值之间具有大小关系，所以如果根节点保持不变，左右子树始终分隔两岸，则无论如何调整节点位置，二叉树始终不可能恢复平衡。所以需要更换根节点，使得新的根节点的左右子树的高度趋于平衡。

该情况下需要对平衡二叉树执行右旋操作：

设置根节点 $root$ 的左子节点为新的根节点 $root_{new}$ ；
将 $root_{new}$ 节点的右子树作为 $root$ 节点的左子树，将 $root$ 节点作为 $root_{new}$ 的右子树，即降低“左子树”高度，提升“右子树”高度，使得新的左右子树高度趋于平衡；

对于图 LL_1，节点 $B$ 的平衡因子为 $1$ ，设 $B$ 节点的左子树 $D$ 高度为 $h$ ，则右子树 $E$ 高度为 $h-1$ ，因为 $A$ 的平衡因子为 $2$ ，所以二叉树 $C$ 的高度为： $h-1$ 。则右旋操作后， $B$ 的左子树高度不变为 $h$ ，右子树高度为： $1+max(height(C),height(E))=h$ ，此时二叉树为平衡二叉树，如下图 balanced_LL_1。

balanced_LL_1

对于图 LL_2，节点 $B$ 的平衡因子为 $0$ ，设 $B$ 节点的左右子树高度为 $h$ ，则二叉树 $C$ 的高度为： $h-1$ 。右旋操作后， $B$ 的左子树高度不变为 $h$ ，右子树高度为： $1+max(height(C),height(E))=h+1$ ，此时二叉树为平衡二叉树，如下图 balanced_LL_2。