题目

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

本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 **1** 。

示例 1：
image.png

  1. 输入：root = [3,9,20,null,null,15,7]
  2. 输出：true

示例 2：
image.png

  1. 输入：root = [1,2,2,3,3,null,null,4,4]
  2. 输出：false

示例 3：

  1. 输入：root = []
  2. 输出：true

提示：

  • 树中的节点数在范围 [0, 5000] 内

  • -10^4 <= Node.val <= 10^4

    解题方法

    求解树的高度需要使用 后序遍历。

    递归（自底向上）

    递归判断个子树的高度差，若是子树是平衡二叉树，返回该树的高度；反之返回-1。
    时间复杂度O(n)，空间复杂度O(logn)
    C++代码：

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   int get_height(TreeNode* cur) {
    15.       if(!cur)    return 0;
    17.       int left_height = get_height(cur->left);
    18.       if(left_height==-1)     return -1;
    19.       int right_height = get_height(cur->right);
    20.       if(right_height==-1)    return -1;
    22.       if(abs(left_height-right_height)>1) return -1;
    23.       else    return (1+max(left_height, right_height));
    24.   }
    26.   bool isBalanced(TreeNode* root) {
    27.       int result = get_height(root);
    28.       if(result==-1)  return false;
    29.       else    return true;
    30.   }
    31. };

    迭代（自顶向下）

    模拟后续遍历，遍历二叉树，对父节点的左右子树判断高度差。
    时间复杂度O(n^2)，空间复杂度O(n^2)
    C++代码：

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   int getdepth(TreeNode* cur) {
    15.       queue<TreeNode*> nodes;
    16.       if(!cur)    return 0;
    17.       int depth = 0;
    18.       nodes.push(cur);
    19.       while(nodes.size()>0) {
    20.           depth++;
    21.           int size = nodes.size();
    22.           for(int i=0; i<size; i++) {
    23.               if(nodes.front()->left)     nodes.push(nodes.front()->left);
    24.               if(nodes.front()->right)    nodes.push(nodes.front()->right);
    25.               nodes.pop();
    26.           }
    27.       }
    29.       return depth;
    30.   }
    32.   bool isBalanced(TreeNode* root) {
    33.       stack<TreeNode*> nodes;
    35.       if(!root)   return true;
    36.       nodes.push(root);
    37.       while(nodes.size()>0) {
    38.           TreeNode* cur = nodes.top();
    39.           nodes.pop();
    40.           if(abs(getdepth(cur->left)-getdepth(cur->right))>1)     return false;
    41.           if(cur->right) nodes.push(cur->right);
    42.           if(cur->left)  nodes.push(cur->left);
    43.       }   
    45.       return true;
    46.   }
    47. };