二叉树 - 遍历¶

快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历

2 种方法实现二叉树的前序遍历。¶

递归和非递归

按层打印二叉树¶

输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。例如输入

输出 8 6 10 5 7 9 11

二元树的深度¶

题目：输入一棵二元树的根结点，求该树的深度.从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。例如：输入二元树：

                                     10
                                  /     \
                                 6        14
                              /         /   \
                             4         12     16

输出该树的深度 3。

分析：这道题本质上还是考查二元树的遍历。对于一颗完全二叉树，要求给所有节点加上一个 pNext 指针，指向同一层的相邻节点；如果当前节点已经是该层的最后一个节点，则将 pNext 指针指向 NULL；给出程序实现，并分析时间复杂度和空间复杂度。

二元树的最小深度¶

例如：输入二元树：

输出该树的最小深度 2。

完全二叉树的节点个数¶

判断整数序列是不是二元查找树的后序遍历结果¶

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回 true，否则返回 false。

例如输入 5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

因此返回 true。如果输入 7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回 false。