请完成一个函数，输入一个二叉树，该函数输出它的镜像。 方法1：递归遍历 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ TreeNode* Mirror(TreeNode* pRoot) { TreeNode* temp; if(pRoot==NULL) { return pRoot; } temp=pRoot->left; pR...

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” //方法：递归+二叉搜索树性质+最近公共祖先性质  /*     二叉搜索树:          可以快速地找出树中的某个节点以及从根节点到该节点的路径，例如我们需要找到节点 pp：                  我们从根节点开始遍历；                          如果当前节点就是 pp，那么成功地找到了节点；     ...

题目描述： 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 //方法：递归+最近公共祖先特点  /*     从左右子树分别进行递归，即查找左右子树上是否有p结点或者q结点，就一共有4种情况：          第一种情况：左子树和右子树均找没有p结点或者q结点；或者当前就是p/q;           第二种情况：左子树上没找到，返回右子树的查找结果；          第三种情况：右子树上没找到，返回左子树的查找结果；          第四种情况：左右子树上均能找到，说明此时的p结点和q结点分居root结点两侧，此时就应当直接返回root结点了。 */ TreeNode* lo...

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 //方法：递归  /*     若满足对称二叉树，必须满足:     1. L->val == R->val     2. L->left->val == R->right->val     3. L->right->val == R->left->val          因此可以自顶向下，递归求解即可。     设置一个递归函数isSame(r1, r2),表示如果对称，返回true，否则返回false     递归终止条件：r1==n...

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。 //方法1：递归 int TreeDepth(TreeNode* pRoot) { if(pRoot==NULL) { return 0; } return TreeDepth(pRoot->left)>TreeDepth(pRoot->right)?TreeDepth(pRoot->left)+1:TreeDepth(pRoot->right)+1; } //方法2：分治 int TreeDepth(TreeNode* pRoot) ...

给定一棵二叉搜索树，请找出其中第k大的节点。 //方法1：递归中序遍历 int count=0;//记录遍历了多少个 TreeNode* kNode=NULL; //记录下节点 void midOrder(TreeNode* root,int k) { if(root) { midOrder(root->left,k); count++; if(count==k) { kNode=root; } midOrder(root->right,k); } } TreeNode* KthNode(TreeNode* pRoot, int k) { midOrder(pRoot,k); re...

广度优先搜索（也称宽度优先搜索，缩写BFS）是连通图的一种遍历策略。它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域。 BFS算法是利用队列实现的一种搜索算法，逐层向下遍历，从一个点像四周扩散（将可选节点存放于队列中，删除已被使用的节点），使用队列完成操作，通常用于最短路径的寻找。。 一般可以用它做什么呢？一个最直观经典的例子就是走迷宫，从起点开始，找出到终点的最短路程，很多最短路径算法就是基于广度优先的思想成立的。 BFS 的应用一：层序遍历 层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。 BFS 的应用二：最短路径 ...

描述 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）。 //方法1：BFS+队列  vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int>> res;//输出数组 if(pRoot==NULL) { return res; } queue<TreeNode*> q;//队列 int level=0;//层数 q.push(pRoot); while(!q.empty()) { int q_size=q.size()...

#include<iostream> #include<string> using namespace std;  int main() {     string str = "";     getline(cin, str);     int pos = str.rfind(" ");//找到最后一个空格标记下标     int ans = 0;     ans = st...

描述 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 注：我们约定空树是平衡二叉树。 //方法1：自顶向下 /*     求出以每个结点为根的树的高度，然后再根据左右子树高度差绝对值小于等于1，,就可以判断以每个结点为根的树是否满足定义。      */ int num_tree(TreeNode* root) { if(root==NULL) { return 0; }...

读入一个字符串str，输出字符串str中的连续最长的数字串。 #include<iostream> #include<string> using namespace std; int main() { string str; cin >> str; int max_num = 0,cur_num=0; int start = 0; string s = ""; int cur = 0; while (cur < str.size()) { while (str[cur] >= '0'&&str[cur] &lt...

找出n个数里最小的k个数 #include<iostream> #include<vector> #include<algorithm> #include<cstdio> #pragma warning (disable: 4996) using namespace std; int main() { vector<int> num; int k = 0; int temp; while (scanf("%d",&temp)==1) { num.push_back(temp); } k = num[num....

题目描述： 某比赛已经进入了淘汰赛阶段,已知共有n名选手参与了此阶段比赛，他们的得分分别是a_1,a_2….a_n,小美作为比赛的裁判希望设定一个分数线m，使得所有分数大于m的选手晋级，其他人淘汰。 但是为了保护粉丝脆弱的心脏，小美希望晋级和淘汰的人数均在[x,y]之间。 显然这个m有可能是不存在的，也有可能存在多个m，如果不存在，请你输出-1，如果存在多个，请你输出符合条件的最低的分数线。 #include<iostream> #include<vector> #include<algorithm> using namespace std; int mai...

我们称一个长度为n的序列为正则序列，当且仅当该序列是一个由1~n组成的排列，即该序列由n个正整数组成，取值在[1,n]范围，且不存在重复的数，同时正则序列不要求排序 有一天小团得到了一个长度为n的任意序列s，他需要在有限次操作内，将这个序列变成一个正则序列，每次操作他可以任选序列中的一个数字，并将该数字加一或者减一。 请问他最少用多少次操作可以把这个序列变成正则序列？ /* 思路： 先把所有比1小的都改到1，比n大的都改到n。 然后排序，让每个数字都改成下标对应，步数是一样的。 */ #include<iostream> #include<vector> #includ...