网站用vps做dns,爱网恋的男生,赶集网网站建设ppt模板,陆金所网站开发二部力扣日记#xff1a;【二叉树篇】平衡二叉树 日期#xff1a;2023.11.30 参考#xff1a;代码随想录、力扣 110. 平衡二叉树
题目描述 难度#xff1a;简单 给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。
本题中#xff0c;一棵高度平衡二叉树定义为#…力扣日记【二叉树篇】平衡二叉树 日期2023.11.30 参考代码随想录、力扣 110. 平衡二叉树
题目描述 难度简单 给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1 输入root [3,9,20,null,null,15,7] 输出true 示例 2 输入root [1,2,2,3,3,null,null,4,4] 输出false 示例 3 输入root [] 输出true 提示
树中的节点数在范围 [0, 5000] 内-10^4 Node.val 10^4
题解
/*** 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 {
#define SOLUTION 2
public:
#if SOLUTION 1 // 一颗高度平衡二叉树需要保证(每个节点的左右子树的高度差绝对值不超过1)即要满足每个节点二叉树都是平衡二叉树bool isBalanced(TreeNode* root) {// 输入参数当前节点返回值当前节点二叉树是否是完全平衡二叉树// 终止条件1. 节点为空是2.节点左右子树绝对值大于1不是(有一个节点不满足绝对值条件则一定不是平衡二叉树)if (root nullptr) return true;int leftDepth getDepth(root-left);int rightDepth getDepth(root-right);if (abs(leftDepth - rightDepth) 1) return false;// 递归逻辑如果当前节点满足左右子树绝对值不超过1则递归判断左右节点是否是平衡二叉树// 当左右节点都是完全平衡二叉树(说明其子节点也都是完全平衡二叉树),则当前节点是完全平衡二叉树// 递归判断return isBalanced(root-left) isBalanced(root-right);}int getDepth(TreeNode * node) {if (node nullptr) return 0;// 左子树的高度 左子树根节点的最大深度int leftDepth getDepth(node-left);int rightDepth getDepth(node-right);return 1 max(leftDepth, rightDepth);}
#elif SOLUTION 2// 上面的方法实际上用了两层递归每次判断高度都用了一次递归造成额外开销(虽然从最终执行结果看两者并没有太大区别)// 可以通过设置返回值为 -1 来表示当前节点是否是平衡二叉树来提前终止递归而不用重新判断int getHeight(TreeNode* node) {// 输入参数当前节点返回值当前节点子树的高度如果是-1则表示当前节点子树不是平衡二叉树// 终止条件if (node nullptr) return 0;// 递归逻辑// 分别求出其左右子树的高度然后如果差值小于等于1则返回当前二叉树的高度// 否则返回-1表示已经不是二叉平衡树了。int leftHeight getHeight(node-left);if (leftHeight -1) return -1; // 在这里提前判断就不用继续递归右节点(因为不平衡没有必要再计算高度了)int rightHeight getHeight(node-right);if (rightHeight -1) return -1; // 提前判断if (abs(leftHeight - rightHeight) 1) return -1;else return 1 max(leftHeight, rightHeight);}bool isBalanced(TreeNode* root) {if (root nullptr) return true;return getHeight(root) -1 ? false: true;}
#endif
};复杂度
时间复杂度 空间复杂度
思路总结
