Construct binary tree from preorder and inorder traversal
题目描述
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
思路
关于根据前序和中序如何得到二叉树的结构的计算方式，我就不重复了，之前的程序里面也有，这里就只说说代码里几个参数的思路。
一定要做边界条件的判断！
| 1 2 3 | root->left = build(preorder, pstart + 1, pstart + i - istart, inorder, istart, i - 1); root->right = build(preorder, pstart + i - istart + 1, pend, inorder, i + 1, iend); |
对于左子树处理来说，中序遍历所要处理的位置就是根节点左侧的所有数字，所以自然起始位置就是istart，结束位置就是i-1；对于前序遍历来说表示就麻烦一些，起始位置还好，是pstart+1,结束位置是pstart+(i-istart)，其中i-istart是左子树的元素数。
对于右子树处理来说，中序遍历所要处理的位置就是根节点右侧的所有数字，所以自然起始位置就是i+1，结束位置就是iend；对于前序遍历来说，就是从左侧子树最后一个元素后面那个数字到最后一个，所以起始位置是pstart + i - istart + 1，结束位置是pend。
代码实现
| 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 | TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { int presize = preorder.size(); int insize = inorder.size(); if (presize == 0 || insize == 0) { return NULL; } else if (presize != insize) return NULL; return build(preorder, 0, presize - 1, inorder, 0, insize - 1); } TreeNode* build(vector<int>&preorder, int pstart, int pend, vector<int>&inorder, int istart, int iend) { if (pstart > pend || istart > iend) return NULL; int mid = preorder[pstart]; TreeNode* root = new TreeNode(mid); int i = istart; for (; i <= iend; ++i) { if (inorder[i] == mid) break; } root->left = build(preorder, pstart + 1, pstart + i - istart, inorder, istart, i - 1); root->right = build(preorder, pstart + i - istart + 1, pend, inorder, i + 1, iend); return root; } |
binary tree level order traversal ii
题目描述
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
题目解析
代码实现
| 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 | vector<vector<int> > levelOrderBottom(TreeNode *root) { vector<vector<int> >result; if(root==nullptr) return result; vector<int> temp; TreeNode *last=root; TreeNode *p; queue<TreeNode *>q; q.push(root); while(!q.empty()) { p=q.front(); temp.push_back(p->val); q.pop(); if(p->left) q.push(p->left); if(p->right) q.push(p->right); if(p==last) { result.push_back(temp); temp.clear(); last=q.back(); } } reverse(result.begin(),result.end()); return result; } |
Minimum path sum
题目描述
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.Note: You can only move either down or right at any point in time.
题目解析
代码实现
| 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 | int minPathSum(vector<vector<int> > &grid) { int row = grid.size();//多少行 int col = grid[0].size();//多少列 vector<vector<int> >dp(row, vector<int>(col, 0)); dp[0][0] = grid[0][0]; //第一行 for (int i = 1; i < col; i++) { dp[0][i] = dp[0][i - 1] + grid[0][i]; } //第一列 for (int i = 1; i < row; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[row-1][col-1]; } |
