输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。思路平衡二叉树中每个节点的平衡因子只有三种可能：-1，0，1。遍历二叉树，只要有一个节点的平衡因子不是-1,0,1则二叉树的不是平衡二叉树，否则就是。比较直观的思路就是计算每个节点的左右子树的高度，然后看是否平衡。但是这样，时间复杂度为O(n2)，节点被重复遍历了。可以一遍遍历一遍统计，可以用遍历时，统计节点的高度，如果是不平衡的节点，设置其高度为-1，否则就是正常高度值。代码class Solution { public: int height(TreeNode* root) { if(root == nullptr) { return 0; } int left = height(root->left); int right = height(root->right); if(left == -1 || right == -1 ||

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。思路二叉树的深度等于左子树的深度和右子树的深度较大值加一代码class Solution { public: int maxDepth(TreeNode* root) { if(root == nullptr) return 0; return max(maxDepth(root->left),maxDepth(root->right))+1; } };

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。思路中序遍历结果就是二叉搜索树的排序结果，如果第一大是最小的数，就是正常的中序遍历。如果第一大是最大的数，就是中序遍历的到序，遍历时，先遍历右子树，再遍历左子树。代码class Solution { private: TreeNode* desNode; int ak; public: void kLargest(TreeNode* root) { if(root == nullptr || ak <= 0) return; kLargest(root->right); if(--ak == 0) { desNode = root; } kLargest(root->left); } int kthLargest(TreeNode* root, int k) { if(root == nullptr) return INT_MIN;

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。思路二分法，每次求取中间数的下标，并和下标对应的数比较，如果相等，则表示数字在中间数的右边，如果不等，则表示在中间数的左边。逐渐逼近，最后得到结果。代码class Solution { public: int missingNumber(vector<int>& nums) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (mid == nums[mid]) { left = mid + 1; } else { right = mid - 1

统计一个数字在排序数组中出现的次数思路：排序数组，如果出现多个相同数字，则这些数字都在一起，找到第一个和最后一个数字就可以得出次数代码：class Solution { public: int search(vector<int>& nums, int target, bool leftBegin) { int left = 0, right = nums.size()-1,ans = nums.size(); while(left <= right) { int mid = left + (right-left)/2; if(nums[mid] > target || (leftBegin && nums[mid] == target)) { right = mid - 1; ans = mid; } else {