第一题
- Given a linked list,
- determine
- if it has a cycle in it.Follow up: Can you solve it without using extra space ?
- /**
- * Definition for singly-linked list.
- * struct ListNode {
- * int val;
- * ListNode *next;
- * ListNode(int x) : val(x), next(NULL) {}
- * };
- */
- class Solution {
- public: bool hasCycle(ListNode * head) {
- if (head == NULL) return false;
- ListNode * slow = head;
- ListNode * fast = head;
- while (fast - >next && fast - >next - >next) {
- slow = slow - >next;
- fast = fast - >next - >next;
- if (slow == fast) return true;
- }
- return false;
- }
- };
第二题
二分查找
- int searchInsert(int A[], int n, int target) {
- int low = 0,
- high = n - 1;
- int mid = 0;
- while (low <= high) {
- mid = low + (high - low) / 2;
- if (A[mid] == target) return mid;
- else if (A[mid] < target) low = mid + 1;
- else high = mid - 1;
- }
- return low;
- }
第三题
- class Solution {
- public: int uniquePaths(int m, int n) {
- int a[m][n];
- a[0][0] = 1;
- a[0][1] = 1,
- a[1][0] = 1;
- a[1][1] = 2;
- for (int j = 0; j < n; j++) a[0][j] = 1;
- for (int i = 0; i < m; i++) a[i][0] = 1;
- for (int i = 1; i < m; i++) {
- for (int j = 1; j < n; j++) {
- a[i][j] = a[i - 1][j] + a[i][j - 1];
- }
- }
- return a[m - 1][n - 1];
- }
- };
第四题
- class Solution {
- public:
- void sortColors(int A[], int n) {
- int zero = 0,two=n-1;
- for(int i=0;i<n;i++)
- {
- while(i<two && A[i]==2) swap(A[i],A[two--]);
- while(i>zero && A[i]==0) swap(A[i],A[zero++]);
- }
- }
- };
第五题
二叉树的中序遍历的非递归形式
- class Solution {
- public: vector < int > inorderTraversal(TreeNode * root) {
- vector < int > v;
- if (root == NULL) return v;
- TreeNode * p = root;
- stack < TreeNode * >stk;
- while (p || !stk.empty()) {
- if (p) {
- stk.push(p);
- p = p - >left;
- } else {
- p = stk.top();
- stk.pop();
- v.push_back(p - >val);
- p = p - >right;
- }
- }
- return v;
- }
- };
第六题
(层序遍历的应用)
- /**
- * Definition for binary tree with next pointer.
- * struct TreeLinkNode {
- * int val;
- * TreeLinkNode *left, *right, *next;
- * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
- * };
- */
- class Solution {
- public:
- void connect(TreeLinkNode *root) {
- if(root == nullptr) return;
- queue<TreeLinkNode*> q;
- TreeLinkNode* temp,*tail = root;
- q.push(root);
- while(!q.empty()) {
- temp = q.front();
- q.pop();
- if(temp->left)
- q.push(temp->left);
- if(temp->right)
- q.push(temp->right);
- if(temp == tail) {
- temp->next = nullptr;
- tail = q.back();
- }
- else {
- temp->next = q.front();
- }
- }
- }
- };
第七题
递归写法
- class Solution {
- public:
- bool hasPathSum(TreeNode *root, int sum) {
- if(!root) return false;
- if(root->left == NULL && root->right == NULL && sum - root->val == 0)
- return true;
- return hasPathSum(root->left,sum - root->val) || hasPathSum(root->right,sum - root->val);
- }
- };
非递归写法
- class Solution {
- public: bool hasPathSum(TreeNode * root, int sum) {
- if (!root) return false;
- queue < TreeNode * >q;
- queue < int > sum_q;
- q.push(root);
- sum_q.push(root - >val);
- while (!q.empty()) {
- TreeNode * cur = q.front();
- q.pop();
- int temp = sum_q.front();
- sum_q.pop();
- if (cur - >left == nullptr && cur - >right == nullptr && temp == sum) {
- return true;
- }
- if (cur - >left) {
- q.push(cur - >left);
- sum_q.push(temp + cur - >left - >val);
- }
- if (cur - >right) {
- q.push(cur - >right);
- sum_q.push(temp + cur - >right - >val);
- }
- }
- return false;
- }
- };
第八题 ((-_-), 写指针写烦了, 换 java)
- public class Solution {
- public boolean isSameTree(TreeNode p, TreeNode q) {
- if (p == null && q == null) return true;
- if (p == null || q == null) return false;
- if (p.val != q.val) return false;
- return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
- }
- }
第九题 二叉树的先序遍历 (非递归实现)
- /**
- * Definition for binary tree
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- import java.util. * ;
- public class Solution {
- public ArrayList < Integer > preorderTraversal(TreeNode root) {
- ArrayList < Integer > al = new ArrayList < Integer > ();
- if (root == null) return al;
- Stack < TreeNode > s = new Stack < TreeNode > ();
- s.push(root);
- while (!s.empty()) {
- TreeNode temp = s.pop();
- al.add(temp.val);
- if (temp.right != null) s.push(temp.right);
- if (temp.left != null) s.push(temp.left);
- }
- return al;
- }
- }
来源: http://www.jianshu.com/p/a16daede514a