剑指 Offer 55 - II. 平衡二叉树

题目描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

解题思路

  • 判定二叉树是否是平衡二叉树，就要对每个节点，比较其左子树深度和右子树深度
  • 如果左右子树深度之差大于1，那么就不是平衡二叉树
  • 在具体实现上，如果自顶向下递归，那么求高度的函数需要遍历一次二叉树、递归判断平衡性的函数也要多次遍历二叉树，遍历的复杂度会提高到O(N^2)
  • 可以用自底向下的递归，先求取左右子树的高度并判断平衡性
  • 在求高度的函数中，使用-1来标记不平衡的情况，一旦发现就递归返回-1

复杂度分析

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

知识点

二叉树，递归，平衡二叉树

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     // 自底向上递归
  13.     // 如果发现不平衡，则递归返回-1
  14.     int getDepth(TreeNode* root) {
  15.         if (!root) {
  16.             return 0;
  17.         }
  18.         int leftDepth = getDepth(root->left);
  19.         int rightDepth = getDepth(root->right);
  20.         if (-1 == leftDepth || -1 == rightDepth || abs(leftDepth - rightDepth) > 1) {
  21.             return -1;
  22.         }
  23.         return max(leftDepth, rightDepth) + 1;
  24.     }
  26.     bool isBalanced(TreeNode* root) {
  27.         if (!root) {
  28.             return true;
  29.         }
  30.         return getDepth(root) >= 0;
  31.     }
  32. };