最大堆和最小堆 一、堆树的定义堆树的定义如下： 堆树是一颗完全二叉树； 堆树中某个节点的值总是不大于或不小于其孩子节点的值； 堆树中每个节点的子树都是堆树。当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。如下图所示，第一个图为最大堆，第二个为最小堆。 二、堆树的操作以最大堆为例进行讲解，最小堆同理。 原始数据为a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}，采用顺序存储方式，对应的完全二叉树如下图所示： 构造最…

merge sorted array 题目描述 Given two sorted integer arrays A and B, merge B into A as one sorted array.Note:  You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are mand n respectively. 题目解析 由于…

n queens ii 题目描述 Follow up for N-Queens problem.Now, instead outputting board configurations, return the total number of distinct solutions. 题目解析 我们令x[i]的值为第i个皇后所在的列数。那么我们第一个皇后的位置可以在第一行任意一个位置任选，所以我们试出来第一个皇后在第1到第n个列位置下的不同情况（一共有n颗n叉树）。然后安排完第一个皇后位置后，第二个皇后位置在第二行也是…

题目描述 Given n, how many structurally unique BST's (binary search trees) that store values 1...n?For example, Given n = 3, there are a total of 5 unique BST's. 题目解析 我们可以发现，只需求出左、右子树各有多少种，二者相乘即为以 i 作为root时BST的总数。所以我们可以用动态规划来实现。当节点数为0个的时候，子树为0个，节点为1个的时候，子树为1个，节点数为…

题目描述 Given a roman numeral, convert it to an integer.Input is guaranteed to be within the range from 1 to 3999. 题目解析 罗马数字的规律如下： 罗马数字 阿拉伯数字 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 另外还要注意的是： - 相同的数字连写、所表示的数等于这些数字相加得到的数、如：Ⅲ=3； - 小的数字在大的数字的右边、所表示的数等于这些数字相加得到的数、 如：Ⅷ=8…

题目描述 Given two binary trees, write a function to check if they are equal or not.Two binary trees are considered equal if they are structurally identical and the nodes have the same value. 思路说明 其实这个题非常简单，算是判断一个树是不是另一个树子树的基础版，不需要调用另一个子程序，直接递归自己这个程序即可。就是判断树上每一个结点…

题目描述 题目描述 Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set toNULL. Initially, all…