Algorithm

题目： Given a binary tree, return the postorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [3,2,1] Follow up: Recursive solution is trivial, could you do it iteratively? 解题： 遍历顺序“根-左-右” 实现： 使用栈实现 从根节点开始，先将根节点压入栈，保存结果值，然后移动到右节点， 保证“根-右边”顺序， 为空后出栈，取其左节点入栈中。这样入栈就保证了访问顺序为“根-右-左”， 出栈实现“左-右-根”。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> ss; TreeNode *p= root, *t; while(!ss.empty()||p){ if (p){ ss.push(p); res.insert(res.begin(), p->val); p = p->right; } else { p=ss.top(); ss.pop(); p= p->left; } } return res; } }; 实现： 递归实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector <int> res; postorder(root, res); return res; } void postorder(TreeNode *root, vector<int> &res){ if (!root) { return; } if (root->left) { postorder(root->left, res); } if (root->right){ postorder(root->right, res); } res.push_back(root->val); } }; 参考: [LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历

题目： Given a binary tree, return the inorder traversal of its nodes’ values. Example: Input: 1 2 3 4 5 6 [1,null,2,3] 1 \ 2 / 3 Output: 1 [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? 解题： 遍历顺序“根-左-右” 实现： 使用栈实现 从根节点开始，先将根节点压入栈，保存结果值，然后移动到左节点， 保证“根-左”顺序， 为空后出栈，取其右节点入栈中。这样就保证了访问顺序为“根-左-右”。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> ss; TreeNode *p = root; while (!ss.empty()||p){ if (p!=NULL){ ss.push(p); res.push_back(p->val); p = p->left; } else{ p = ss.top(); ss.pop(); p=p->right; } } return res; } }; 实现： 递归实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; preorder(root, res); return res; } void preorder(TreeNode *root, vector<int> &res){ if (!root) return; res.push_back(root->val); preorder(root->left, res); preorder(root->right, res); } }; 参考: [LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历 ...

题目： There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room. Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v. ...

题目： Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1. Example 1: Input: 1 2 3 [[0,0,0], [0,1,0], [0,0,0]] Output: 1 2 3 [[0,0,0], [0,1,0], [0,0,0]] Example 2: 1 2 3 4 Input: [[0,0,0], [0,1,0], [1,1,1]] Output: 1 2 3 [[0,0,0], [0,1,0], [1,2,1]] Note: ...

题目： An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535). Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image. To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor. ...

题目： Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4]. ...

题目： Implement the following operations of a stack using queues. push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. empty() – Return whether the stack is empty. Example: 1 2 3 4 5 6 7 MyStack stack = new MyStack(); stack.push(1); stack.push(2); stack.top(); // returns 2 stack.pop(); // returns 2 stack.empty(); // returns false Notes: ...

题目： Implement the following operations of a queue using stacks. push(x) – Push element x to the back of queue. pop() – Removes the element from in front of queue. peek() – Get the front element. empty() – Return whether the queue is empty. Example: 1 2 3 4 5 6 7 MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false Notes: ...

题目： Given a binary tree, return the inorder traversal of its nodes\’ values. Example: Input: 1 2 3 4 5 6 [1,null,2,3] 1 \ 2 / 3 Output: 1 [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? 解题： 树的中序遍历： 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。 a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。 b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。 重复以上1、2直到当前节点为空。 实现： 递归方式： 对左子结点调用递归函数，根节点访问值，右子节点再调用递归函数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector <int> res; inorder(root, res); return res; } void inorder(TreeNode *root, vector<int> &res){ if (!root) { return; } if (root->left) { inorder(root->left, res); } res.push_back(root->val); if (root->right){ inorder(root->right, res); } } }; 空间复杂度：O(n)， 时间复杂度：O(n)。 使用栈实现 从根节点开始，先将根节点压入栈，然后再将其所有左子结点压入栈，然后取出栈顶节点，保存节点值，再将当前指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子结点压入栈中。这样就保证了访问顺序为左-根-右， ...

题目： You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Example 1: 1 2 3 4 5 6 7 8 9 10 11 Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. Note: ...