手撸二叉树之平衡二叉树

手撸二叉树之平衡二叉树

今天给大家带来的有关二叉树的算法题为平衡二叉树，正文如下。

题目：

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。