最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

【天天新要闻】判断二叉树是否为平衡二叉树

来源：博客园


(资料图)

问题：判断二叉树是否为平衡二叉树面试题55 - II. 平衡二叉树（从底至顶、从顶至底，清晰图解） - 平衡二叉树 - 力扣（LeetCode）

方法一：后序遍历+剪枝，自下而上

后续遍历节点，递归向上返回子树的深度，同时判断当前子树是否为平衡二叉树，若不是则直接返回，称为剪枝。

recur(TreeNode* node)函数:当前子树的深度= 左右子树的深度最大值+1；当前子树左右子树深度差 >1则直接返回，不是平衡二叉树

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

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

方法二：前序遍历+深度，自顶向下

此方法会造成大量重复计算；自顶向下判断每个节点的深度差<=1，每个节点至少一次被访问；

判断当前子树是否为平衡二叉树；判断当前子树的左子树是否是平衡二叉树；判断当前子树的右子树是否是平衡二叉树；

Depth(TreeNode* node)计算当前节点的深度，返回左右子树深度的最大值+1；

时间复杂度：O(N logN);空间复杂度：O(N)；

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

关键词： 平衡二叉树 空间复杂度 时间复杂度