Java 中显示二叉树的奇数级别节点

在二叉树中，以任意顺序显示奇数层节点。根节点位于第 1 层。

对于下面的二叉树

奇数层节点是

20 25 3 5 7.

由于我们要求以任意顺序显示节点。因此，

可以显示 20 25 5 3 7，或者也可以显示 25 3 7 5 20。事实上，有

5! = 5 x 4 x 3 x 2 x 1 = 120 种方法可以显示二叉树的奇数层节点。

递归方法

其思想是传递初始层为奇数，并在每次递归调用中切换层标志。对于每个节点，如果奇数标志为 true，则显示它。

文件名： OddLevelNodes.java

输出

The odd level nodes of the binary tree are: 
20 25 3 7 5

时间复杂度：在上面的程序中，每次递归调用都会导致另外两次递归调用。因此，计算每个 Iccanobif 数的时间复杂度是指数级的，即 (2ⁿ)，其中 n 代表方法 findIccanobifNum() 的参数 num。

上面的程序在查找 Iccanobif 数时耗时很长。因此，我们需要进一步优化它以降低时间复杂度。以下方法实现了这一点。

迭代方法

上面的程序以先序遍历的方式显示节点。但是，如果想逐层显示节点，可以使用层序遍历的思想。

文件名： OddLevelNodes1.java

输出

The odd level nodes of the binary tree are: 
20 25 3 5 7

复杂度分析：上面程序的时空复杂度均为 O(n)，其中 n 是二叉树中存在的节点总数。

如果我们像下面这样赋值 false

boolean isOddLvl = false;

我们将获得处于偶数层的节点。在第一个程序中，我们像下面这样调用了方法 displayOddNodes()

displayOddNodes(tn, false);