欢迎光临
我们一直在努力

Leetcode110.平衡二叉树

Problem:
110. 平衡二叉树

思路

自顶向下递归:1. 对每个节点,分别计算左右子树的高度 2. 检查当前节点是否平衡(左右高度差 ≤ 1) 3.递归检查左右子树是否平衡

复杂度

  • 时间复杂度: O(n2)O(n^2) O(n2)(最坏情况(链表状树):第1层:遍历 n 个节点;第2层:遍历 n-1 个节点…总计:n + (n-1) + … + 1 = O(n²))
    • 空间复杂度: O(n)O(n)O(n)(递归栈深度 = 树的高度,最坏情况(链表):O(n),平衡树:O(log n))

      Code(C++)

      /**
      * Definition for a binary tree node.
      * struct TreeNode {
      * int val;
      * TreeNode *left;
      * TreeNode *right;
      * TreeNode() : val(0), left(nullptr), right(nullptr) {}
      * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
      * };
      */
      class Solution {
      public:
      int height(TreeNode* root){
      if(root==NULL){
      return 0;
      }else{
      return max(height(root->left),height(root->right))+1;
      }
      }
      bool isBalanced(TreeNode* root) {
      if(root==NULL){
      return true;
      }else{
      return abs(height(root->left)-height(root->right))<=1 && isBalanced(root->left) && isBalanced(root->right);
      }
      }
      };

      赞(0)
      未经允许不得转载:171主机测评 » Leetcode110.平衡二叉树
      分享到: 更多 (0)

      评论 抢沙发

      • 昵称 (必填)
      • 邮箱 (必填)
      • 网址