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.

思路

关于根据前序和中序如何得到二叉树的结构的计算方式,我就不重复了,之前的程序里面也有,这里就只说说代码里几个参数的思路。
一定要做边界条件的判断!

对于左子树处理来说,中序遍历所要处理的位置就是根节点左侧的所有数字,所以自然起始位置就是istart,结束位置就是i-1;对于前序遍历来说表示就麻烦一些,起始位置还好,是pstart+1,结束位置是pstart+(i-istart),其中i-istart是左子树的元素数。
对于右子树处理来说,中序遍历所要处理的位置就是根节点右侧的所有数字,所以自然起始位置就是i+1,结束位置就是iend;对于前序遍历来说,就是从左侧子树最后一个元素后面那个数字到最后一个,所以起始位置是pstart + i - istart + 1,结束位置是pend

代码实现

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).

题目解析

代码实现

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.

题目解析

代码实现