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];
}