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.
思路
关于根据前序和中序如何得到二叉树的结构的计算方式,我就不重复了,之前的程序里面也有,这里就只说说代码里几个参数的思路。
一定要做边界条件的判断!
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
。
代码实现
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).
题目解析
代码实现
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.
题目解析
代码实现
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];
}
文章评论