# 剑指Offer-按之字形顺序打印二叉树

```package Tree;

import java.util.ArrayList;
import java.util.Queue;

/**
* 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
* 思路：
* 先按层次输出二叉树
* 判断奇数层和偶数层
* 反转arrayList
*/
public class Solution9 {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
Solution9 Solution9 = new Solution9();
TreeNode treeNode = Solution9.createBinaryTreeByArray(array, 0);
for (ArrayList list :
Solution9.Print(treeNode)) {
System.out.println(list);
}
}

/**
* 之字形打印二叉树
* 用reserve反转，时间复杂度高
*
* @param pRoot
* @return
*/
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
//arrayLists存储结果
ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
if (pRoot == null) {
return arrayLists;
}
ArrayList<Integer> arrayList = new ArrayList<>();
//使用队列，先进先出
int start = 0;
int end = 1;
boolean leftToRight = true;
while (!queue.isEmpty()) {
TreeNode temp = queue.remove();
//添加到本行的arrayList
start++;
//每打印一个节点，就把此节点的下一层的左右节点加入队列，并记录下一层要打印的个数
if (temp.left != null) {
}
if (temp.right != null) {
}

if (start == end) {
start = 0;
end = queue.size();
if (leftToRight) {
} else {

}
leftToRight = !leftToRight;
arrayList = new ArrayList<>();
}
}
return arrayLists;
}

/**
* 反转
*
* @param arrayList
* @return
*/
private ArrayList<Integer> reverse(ArrayList<Integer> arrayList) {
ArrayList<Integer> arrayList1 = new ArrayList<>();
for (int i = arrayList.size() - 1; i >= 0; i--) {
}
return arrayList1;
}

public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}

/**
* 数据转二叉树
*
* @param array
* @param index
* @return
*/
private TreeNode createBinaryTreeByArray(int[] array, int index) {
TreeNode tn = null;
if (index < array.length) {
int value = array[index];
tn = new TreeNode(value);
tn.left = createBinaryTreeByArray(array, 2 * index + 1);
tn.right = createBinaryTreeByArray(array, 2 * index + 2);
return tn;
}
return tn;
}
}```

137 篇文章39 人订阅

0 条评论

## 相关文章

30450

31750

46060

804110

9320

### 剑指Offer-平衡二叉树

package Tree; /** * 平衡二叉树 * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 * 平衡二叉树（Balanced Binary ...

30770

8120

27030

21560

11920