不分层：
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode treeNode = queue.poll();
result.add(treeNode.val);
if (treeNode.left != null) queue.offer(treeNode.left);
if (treeNode.right != null) queue.offer(treeNode.right);
}
return result;
}
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。（分层）
思路一：利用队列，层次遍历的方式，存入list
// 也是分行打印，比上面简洁
public void printEveryLayer(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int layerSize = queue.size();
for (int i = 0; i < layerSize; i++) {
TreeNode node = queue.poll();
System.out.println(node.val+" ");
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
System.out.println();
}
}
/**
* 统计队列中每一层的节点数，循环添加
* @param pRoot
* @return
*/
ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(pRoot);
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
if (pRoot == null) return lists;
ArrayList<Integer> layerList = new ArrayList<>();
while (!queue.isEmpty()){
int layerSize = queue.size();
//每次都将每一行统计完再出循环，进入下一行
for (int i=0;i<layerSize;++i){
TreeNode temp = queue.poll();
layerList.add(temp.val);
if (temp.left != null) queue.offer(temp.left);
if (temp.right != null) queue.offer(temp.right);
}
lists.add(new ArrayList<Integer>(layerList));
layerList.clear();
}
return lists;
}
思路二：
递归构造一个参数为根节点，当前深度，和list的节点。递归左右节点，每次深度加1
/**
* 递归解法
* @param pRoot
* @return
*/
ArrayList<ArrayList<Integer>> Print2(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
depth(pRoot,1,lists);
return lists;
}
private void depth(TreeNode treeNode, int depth, ArrayList<ArrayList<Integer>> lists) {
if (treeNode == null) return;
//深度改变时，才往集合中加入新的list
if (depth > lists.size()){
lists.add(new ArrayList<Integer>());
}
//直接将该节点值接如最后的list中
lists.get(depth-1).add(treeNode.val);
depth(treeNode.left,depth+1,lists);
depth(treeNode.right,depth+1,lists);
}
思路三：设置两个变量，记录层次和每层的数量。
/**
* 思路，增加两个变量分别表示当前行的节点数目和下一行的节点数目
* 每打印一次当前行减一，每添加一次子节点下一行加1
* 当前行为0时赋值下一行，下一行清0
* @param pRoot
* @return
*/
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
int toBePrinted = 1;
int nextLevel = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(pRoot);
if (pRoot == null) return list;
//放在循坏里会变成每次只有一个
ArrayList<Integer> perList = new ArrayList<>();
while (!queue.isEmpty()){
TreeNode temp = queue.poll();
perList.add(temp.val);
toBePrinted--;
if (temp.left != null){
queue.offer(temp.left);
nextLevel++;
}
if (temp.right != null){
queue.offer(temp.right);
nextLevel++;
}
if (toBePrinted == 0){
list.add(new ArrayList<Integer>(perList));
//直接把内存地址清空
perList.clear();
/**
* 或者采用如下注释
*
*/
// list.add(perList);
// perList = new ArrayList<Integer>();
toBePrinted = nextLevel;
nextLevel = 0;
}
}
return list;
}
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
用两个栈去分奇偶行记录下一行，主要体现在出栈存储下一行的区别上
当前奇数行，下一行偶数行要从右向左打印，先记录左节点，右节点先出。
当前偶数行，下一行奇数行从左向右打印，先记录右节点，左节点先出。
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/**
* 两个栈记录不同方向的输出，一个记录奇数行从左到右，一个记录偶数行从右到左，循环打印
* 打印后一行后，改变左右节点的放入顺序，先进先出
* @param pRoot
* @return
*/
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
if (pRoot == null) return lists;
LinkedList<TreeNode> stackOdd = new LinkedList<>();
LinkedList<TreeNode> stackEven = new LinkedList<>();
stackOdd.push(pRoot);
//有一个不为空，则循环继续
while (!stackOdd.isEmpty() || !stackEven.isEmpty()){
ArrayList<Integer> perList = new ArrayList<>();
if (!stackOdd.isEmpty()){
while (!stackOdd.isEmpty()){
TreeNode temp = stackOdd.pop();
perList.add(temp.val);
if (temp.left != null) stackEven.push(temp.left);
if (temp.right != null) stackEven.push(temp.right);
}
}else {
while (!stackEven.isEmpty()){
TreeNode temp = stackEven.pop();
perList.add(temp.val);
if (temp.right != null) stackOdd.push(temp.right);
if (temp.left != null) stackOdd.push(temp.left);
}
}
lists.add(perList);
}
return lists;
}
网友评论