java编程题之从上往下打印出二叉树

import java.util.arraylist;

import java.util.stack;

/**

  *

  * 剑指offer编程题（java实现)——第22题：从上往下打印出二叉树

  *

  * 题目描述

  * 从上往下打印出二叉树的每个节点，同层节点从左至右打印。

  *

  */

public class test22 {

  arraylist<integer> arraylist = new arraylist<>();

  // 每层依次入栈

  stack<treenode> stack1 = new stack<>();

  // 从stack1出栈的元素依次加入stack2，统一通过stack2找到他们的字节点并压入stack1

  stack<treenode> stack2 = new stack<>();

  public arraylist<integer> printfromtoptobottom(treenode root) {

  if (root == null ) {

  return arraylist; // 空则返回

  }

  stack1.push(root);

  while (!stack1.isempty()) {

  while (!stack1.isempty()) {

  treenode tmp = stack1.pop();

  arraylist.add(tmp.val);

  stack2.push(tmp);

  }

  while (!stack2.isempty()) {

  treenode tmp2 = stack2.pop();

  // 从左到右打印，所以右子树先入栈

  if (tmp2.right != null ) {

  stack1.push(tmp2.right);

  }

  if (tmp2.left != null ) {

  stack1.push(tmp2.left);

  }

  }

  }

  return arraylist;

  }

  public class treenode {

  int val = 0 ;

  treenode left = null ;

  treenode right = null ;

  public treenode( int val) {

  this .val = val;

  }

  }

}

//其他方法

/**

public class solution {

  public arraylist<integer> printfromtoptobottom(treenode root) {

   arraylist<integer> list = new arraylist<integer>();

   if(root == null) return list;

   deque<treenode> deque = new linkedlist<treenode>();

   deque.add(root);

   while(!deque.isempty()){

   treenode t = deque.pop();

   list.add(t.val);

   if(t.left != null) deque.add(t.left);

   if(t.right != null) deque.add(t.right);

   }

   return list;

  }

}

*/