力扣|力扣 - 剑指 Offer 55 - II. 平衡二叉树力扣-剑指Offer55-II.平衡二叉树

题目 【力扣|力扣 - 剑指 Offer 55 - II. 平衡二叉树】剑指 Offer 55 - II. 平衡二叉树
思路1（后序遍历+剪枝）

这题是上一题剑指 Offer 55 - I. 二叉树的深度的进阶，逻辑代码和那个一样，也是后续遍历，获取两个子节点较大的那个深度再加上当前一层返回给父节点，是自底向上的
也为要求是否为平很二叉树，要保证他的左子树和右子树差值不大于1，那么我们就在每次获取左右子树的深度的时候再加一个判断就好啦～
但是我们可以进行剪枝优化，如果不剪枝，就算判定为不是平衡二叉树，那么它还是会递归遍历完。当发现不是平衡二叉树的时候，我们返回 -1 ，然后在每次获取完左右子树节点的深度时候，判断是否等于 -1，这样就可以减少不必要的递归了！

代码

class Solution { public boolean isBalanced(TreeNode root) { // 只要返回值不是-1，说明就是平衡二叉树 return dfs(root) != -1; }public int dfs(TreeNode root) { if (root == null) { return 0; }int l = dfs(root.left); // 剪枝，返回 -1 说明不是平衡二叉树了 if (l == -1) { return -1; } int r = dfs(root.right); // 同上 if (r == -1) { return -1; }// 判断左右子树的深度吃的差值是否大于1 if (Math.abs(l - r) > 1) { return -1; }return 1 + Math.max(l, r); } }

复杂度分析

时间复杂度：\(O(N)\)
空间复杂度：\(O(N)\)

思路2（前序遍历）

后序遍历是一种自底向上的方法，只需要遍历一遍链表即可。不过我们也可以使用自顶向下方法，从根节点向下，先判断左右两个子树是否平衡，然后再递归判断子树，不过这样会导致很多节点被重复遍历了，时间复杂度比较高。。

代码

class Solution { public boolean isBalanced(TreeNode root) { if (root == null) { return true; }// 先判断左右两个子树是否平衡，不平衡的话返回false int l = treeDeepth(root.left); int r = treeDeepth(root.right); if (Math.abs(l - r) > 1) { return false; }// 然后在继续判断他的左右子树是否平衡（前序遍历） return isBalanced(root.left) && isBalanced(root.right); }public int treeDeepth(TreeNode root) { if (root == null) { return 0; }int l = treeDeepth(root.left); int r = treeDeepth(root.right); return 1 + Math.max(l, r); } }

复杂度分析