建网站一般要多少钱,怎么注册公司流程和费用,网站流量显示,济南外贸网站建设公司1. 题目
给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。
本题中#xff0c;一棵高度平衡二叉树定义为#xff1a;
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]3/ \9 20/ \15 7
返回 true 。…1. 题目
给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]3/ \9 20/ \15 7
返回 true 。示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]1/ \2 2/ \3 3/ \4 4
返回 false 。限制
1 树的结点个数 10000《剑指Offer》同题面试题55 - II. 平衡二叉树
2. 解题
递归求二叉树左右子树高度当中任何一个的子树高度差超过1停止搜索
class Solution {
public:bool isBalanced(TreeNode* root) {bool bal true;balence(root,bal);return bal;}int balence(TreeNode* root, bool bal) {if(!bal)return -1;if(root NULL)return 0;int left_height balence(root-left,bal);int right_height balence(root-right,bal);if(abs(left_height-right_height)1)bal false;return max(left_height,right_height)1;}
};class Solution {bool balanced true;
public:bool isBalanced(TreeNode* root) {depth(root);return balanced;}int depth(TreeNode* root){if(!balanced || !root)return 0;int depthL depth(root-left);int depthR depth(root-right);if(abs(depthL - depthR) 1)balanced false;return 1max(depthL, depthR);}
};
