题目地址(110. 平衡二叉树)

https://leetcode-cn.com/problems/balanced-binary-tree/

题目描述

  1. 给定一个二叉树，判断它是否是高度平衡的二叉树。
  3. 本题中，一棵高度平衡二叉树定义为：
  5. 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
  9. 示例 1：
  11. 输入：root = [3,9,20,null,null,15,7]
  12. 输出：true
  15. 示例 2：
  17. 输入：root = [1,2,2,3,3,null,null,4,4]
  18. 输出：false
  21. 示例 3：
  23. 输入：root = []
  24. 输出：true
  29. 提示：
  31. 树中的节点数在范围 [0, 5000] 内
  32. -104 <= Node.val <= 104

前置知识


公司

  • 暂无

思路

递归三步曲分析：

  1. 明确递归函数的参数和返回值

参数：当前传入节点。
返回值：以当前传入节点为根节点的树的高度。
那么如何标记左右子树是否差值大于1呢？
如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。
所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。

  1. 明确终止条件

递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0

  1. 明确单层递归的逻辑

如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。
分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则则返回-1，表示已经不是二叉平衡树了。

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public boolean isBalanced(TreeNode root) {
  19.             //如果不等于-1 返回true
  20.             return loop(root) != -1;
  21.         }
  23.         public int loop(TreeNode root) {
  24.             //中止条件
  25.             if (root == null) {
  26.                 return 0;
  27.             }
  28.             //递归调用左右节点 返回左右节点的高度 如果等于-1 就返回-1
  29.             int left = loop(root.left);
  30.             if (left == -1) {
  31.                 return -1;
  32.             }
  33.             int right = loop(root.right);
  34.             if (right == -1) {
  35.                 return -1;
  36.             }
  37.             //求左右节点的高度的绝对值 如果大于1 就说明不是平衡二叉树
  38.             if (Math.abs(left - right) > 1) {
  39.                 return -1;
  40.             }
  41.             //到这一步说明左右平衡 返回当前的高度
  42.             return Math.max(left, right)+1;
  43.         }
  44.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：110. 平衡二叉树 - 图1#card=math&code=O%28n%29&id=oIge1)
  • 空间复杂度：110. 平衡二叉树 - 图2#card=math&code=O%28n%29&id=fgZtL)