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

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

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

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

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

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

LeetCode #222 Count Complete Tree Nodes (完全二叉树节点个数)

题目:

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

 

分析:

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

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

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

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

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

Continue reading LeetCode #222 Count Complete Tree Nodes (完全二叉树节点个数)