Hello, 大家好，今天是我 8 月更文的第 5 天，今天给大家带来的有关二叉树的算法题为平衡二叉树，正文如下。
题目：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
解题思路
这里强调一波概念：
当求二叉树的高度，我们可以使用自底向上的递归方式，自底向上递归的做法类似于后序遍历。
递归分析：
明确递归函数的参数和返回值
参数为传入的节点，返回值要返回传入节点为根节点树的深度那么如何标记左右子树是否差值大于 1 呢。如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。
明确终止条件
递归的过程中依然是遇到空节点了为终止，返回 0，表示当前节点为根节点的高度为 0
明确单层递归的逻辑
如何判断当前传入节点为根节点的二叉树是否是平衡二叉树呢，当然是左子树高度和右子树高度之差。
分别求出左右子树的高度，如果差值小于等于 1，则返回当前二叉树的高度，否则则返回-1，表示已经不是二叉树了。
代码实现
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { // // 自下向上 递归 // public boolean isBalanced(TreeNode root) { // return height(root) >= 0; // }
// public int height(TreeNode root) { // if (root == null) return 0; // int leftHeight = height(root.left); // if (leftHeight == -1) return -1;
// int rightHeight = height(root.right); // if (rightHeight == -1) return -1;
// return Math.abs(leftHeight - rightHeight) > 1 ? -1 : Math.max(leftHeight, rightHeight) + 1; // }
// 更利于理解的思路 private static final int UNBALANCED = -1;
public boolean isBalanced(TreeNode root) { return helper(root) != UNBALANCED; }
public int helper(TreeNode root) { if (root == null) { return 0; }
// 如果左子树不是平衡二叉树，直接返回UNBALANCED int left = helper(root.left); if (left == UNBALANCED) { return UNBALANCED; }
// 如果右子树不是平衡二叉树，直接返回UNBALANCED int right = helper(root.right); if (right == UNBALANCED) { return UNBALANCED; }
// 如果左右子树是平衡二叉树，但是他们的高度相差大于1，直接返回UNBALANCED if (Math.abs(left - right) > 1) { return UNBALANCED; }
// 否则就返回二叉树中节点的最大高度 return Math.max(left, right) + 1; }}
复制代码
最后
复杂度分析
时间复杂度：O(n)，其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)。
空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。
评论