已知前序遍历、中序遍历、后序遍历结果其中之二，生成二叉树

Posted on 2015/08/24 by NeoShell — No Comments ↓

一、已知前序遍历和中序遍历

假设我们用2个数组preorder和inorder来表示前序和中序遍历的结果。

要生成的二叉树的任意子树都对应于preorder和inorder的某个子数组。该子树的根节点对应于preorder子数组的第一个元素，然后在inorder中查找该该元素。对于inorder中的的子数组，根节点元素左侧的子数组对应左子树，右侧的子数组对应右子树。之后使用递归重复该过程。

下面给出一段Java示例代码：

Posted on 2015/08/18 by NeoShell — No Comments ↓

Given a complete binary tree, count the number of nodes.

给定一个完全二叉树的根节点，求该完全二叉树节点的个数。

完全二叉树就是：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。

本题的关键就是求二叉树最后一层的节点个数。对此我们可以使用二分查找。

使用一个整数来表示从根节点到叶子节点的路径，每一位代表方向（0向左，1向右）。例如，1个4层的二叉树，如果路径为5，写成二进制是101，就代表从根节点出发，右，左，右。

通过二分查找，我们可以得到最后一层第一个空节点的位置，也就知道了最后一层有几个几点。然后加上上面几层的节点数就是答案。