题目的主要信息： 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点 方法一： 采用递归。FindPath中用bfs计算以当前结点作为起点满足条件的路径个数，然后递归计算以当前结点的左孩子作为起点的满足条件的路径个数和以右孩子作为起点的满足条件的路径个数。用全局变量count来统计总的路径个数。bfs也是递归函数，如果root为NULL结束递归；否则用sum减去当前结点的值，如果sum变为0，说明这条以root结尾的路径和为sum，count加1.然后再往左右孩子...

题目的主要信息： 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。 方法一： 采用递归。用dfs进行深度优先搜索，首先判断当前结点root是否为NULL，如果不为NULL，就在它的组有子树中递归查找，如果两个节点分别在左右子树中，或者root值为其中一个，另一个值在子树中，则root为最近公共祖先。如果左右子树中有，或者等于当前结点值，则返回true。 具体做法： class Solution { public: TreeNode* ans;//最近公共组先 bool dfs(TreeNode* roo...

题目的主要信息： 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。 方法一： 采用递归。首先判断当前结点是否为NULL，如果是NULL，说明这一条路径不满足条件；否则，sum中减去当前结点的值，如果sum变成了0，且当前结点是叶子结点，说明找到了一条路径。如果sum不为0，则在左右子树递归查找。 具体做法： class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if(!root){//root为NULL结束递归 ...

题目的主要信息： 输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是要求时间复杂度O(n)O(n)O(n)，空间复杂度O(1)O(1)O(1)。 方法一： 采用双指针遍历。left从左边开始遍历数组，right从右边开始遍历数组。首先left遍历一遍所有位于开头的奇数，直到当前数不是奇数时停下，然后right开始从后往前遍历素有的偶数，直到当前数字为奇数时停下。此时，如果left在right的左边，left所指的值为偶数，right所...

题目的主要信息： 输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。 平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 方法一： 采用递归。用dfs递归计算每个结点的高度，如果当前遍历的结点为NULL返回0；否则，递归计算左右子树高度，当前结点的最大高度为左右子树最大高度加1。用IsBalanced_Solution递归判断是否为平衡二叉树，首先用dfs计算左右子树的高度，如果高度差大于1，返回false；否则，继续递归判断左右子树是否为平衡二叉树。 具体做法： class Solution { public: int d...

题目的主要信息： 给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。 方法一： 层次遍历。用队列进行层次遍历，首先将根结点入队。通过一个循环，当队列不为空时，将队列中的元素逐个出列记录在ans中，同时每出列一个结点，就把该结点的左右孩子入列（如果有的话），这样能保证按照层次对树进行遍历。 具体做法： class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vec...

题目的主要信息： 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）。 方法一： 层次遍历。用队列进行层次遍历，首先将根结点入队。通过一个循环，当队列不为空时，将队列中的元素逐个出列记录在ans中，同时每出列一个结点，就把该结点的左右孩子入列（如果有的话），这样能保证按照层次对树进行遍历，但是题目要求的是按照之字形顺序打印，实际上就是在偶数层翻转一下，因此用level记录层次，每当到达偶数层就翻转该层的结点。 具体做法： class Solution { public: vector<vector<int> > Pri...

题目的主要信息： 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 方法一： 用两个指针遍历一遍链表，pre和cur指针。遍历一遍链表，若当前结点cur的值和下一结点相同，表示有重复结点，用一个循环找到当前所有的重复结点的末尾，将pre结点跳连接到下一个不重复的结点上；如果当前结点不是重复结点，则直接往下遍历。 具体做法： class Solution { public: ListNode* deleteDuplication(ListNode* pHead) { ListNode *newHead = new Lis...

题目的主要信息： 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 "go" 时，第一个只出现一次的字符是 "g" 。当从该字符流中读出前六个字符 “google" 时，第一个只出现一次的字符是"l"。 方法一： 采用队列。用q保存第一个不重复的字符Insert函数每输入一个字符，在mp中查找它是否存在，如果不存在的话，表示该字符是第一个输入的，存入q中，然后在mp中更新ch出现个数。FirstAppearingOnce函数首先遍历一遍队列q的头元素，如果该元素在当前字符流中只出现一次，则该字符是字符流中第一个不重复的字符；如果该元素不止出现一次，则把它...

题目的主要信息： 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? 总结题意，就是给定一个1到sum的序列，求所有和为sum的连续序列。 方法一： 暴力枚举。枚举一遍所有起点可能长度的序列，由题可知序列至少两个数，因此每次序列的起点最多为sum/2。计算当前序列之和，如果序列之和等于sum，则保存该序列到到res中，如果序列...

题目的主要信息： 牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？ 总结题意，就是将输入字符串中的单词顺序翻转过来， 方法一： 首先遍历一遍字符串，如果当前字符不是空格，就把它加到temp中；如果当前字符是空格，把temp中的单词存到ans中。这样一遍遍历后，从原始的str中提取...

题目的主要信息： 题目问题：我们可以用 2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2 * 1 的小矩形无重叠地覆盖一个 2 * n 的大矩形，从同一个方向看总共有多少种不同的方法？ 方法一： 采用动态规划。n个矩阵覆盖大矩阵有两种做法： 先用n-1个矩阵覆盖大矩阵，然后把最后一个矩阵竖着***去。 先用n-2个矩阵覆盖大矩阵，然后把最后两个矩阵横着***去。 用动态数组dp[i]表示i个矩阵覆盖大矩阵的方法个数，因此dp[i]=dp[i-1]+dp[i-2]。首先初始化动态数组，然后遍历一遍更新值，最后输出dp[n]。 具体做法： class Solution {...

题目的主要信息： 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。 方法一： 采用递归。如果跳上0级或1级台阶只有一种跳法。否则采用递归，每次可以跳1级或者跳2级、3级……n级，所以总跳法等于所有可能的跳法之和。 具体做法： class Solution { public: int jumpFloorII(int number) { if(number == 0 || number == 1) return 1;//如果是一级台阶或两级台阶只需跳一步 int count = 0;...

题目的主要信息： 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 方法一： 采用递归。如果跳上0级或1级台阶只有一种跳法。否则采用递归，每次可以跳1级或者跳2级，所以总跳法等于先跳一步的跳法加上先跳两步的跳法。 具体做法： class Solution { public: int jumpFloor(int number) { if(number == 0 || number == 1) return 1;//如果是一级台阶或两级台阶只需跳一步 return jumpFloor(...