从上往下打印二叉树的每个节点,同一层的节点按照从左到右的顺序打印。例如输入下图的二叉树,则一次打印出8,6,10,5,7,9,11。
思路:利用队列,将左右子树加入队列末尾,取出结点
代码:
package offer;
import java.util.LinkedList;
import java.util.Queue;
class BineryTree
{
int val;
BineryTree left = null;
BineryTree right = null;
BineryTree(int val)
{
this.val = val;
}
}
public class ti32 {
static void BineryTreeToQueue(BineryTree head)
{
if(head==null)
{
return;
}
Queue<BineryTree> queue = new LinkedList<BineryTree>();
queue.add(head);
while(!queue.isEmpty())
{
BineryTree x = queue.poll();
System.out.println(x.val);
if(x.left!=null)
{
queue.add(x.left);
}
if(x.right!=null)
{
queue.add(x.right);
}
}
}
public static void main(String[] args)
{
BineryTree a = new BineryTree(8);
BineryTree b = new BineryTree(6);
BineryTree c = new BineryTree(10);
BineryTree d = new BineryTree(5);
BineryTree e = new BineryTree(7);
BineryTree f = new BineryTree(9);
BineryTree g = new BineryTree(11);
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
BineryTreeToQueue(a);
}
}
题目三
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
代码:
package offer;
import java.util.ArrayList;
import java.util.Stack;
class BineryTree
{
int val;
BineryTree left = null;
BineryTree right = null;
BineryTree(int val)
{
this.val = val;
}
}
public class ti32 {
static ArrayList<ArrayList<Integer>> BineryTreeToQueue(BineryTree head)
{
ArrayList<ArrayList<Integer>> alist = new ArrayList<>();
if(head==null)
{
return alist;
}
Stack<BineryTree> stack1 = new Stack<BineryTree>();
Stack<BineryTree> stack2 = new Stack<BineryTree>();
stack1.add(head);
while(!stack1.empty()||!stack2.empty())
{
ArrayList<Integer> list = new ArrayList<>();
if(!stack1.empty())
{
while(!stack1.empty())
{
BineryTree x = stack1.pop();
list.add(x.val);
if(x.left!=null)
{
stack2.add(x.left);
}
if(x.right!=null)
{
stack2.add(x.right);
}
}
}
else
{
while(!stack2.empty())
{
BineryTree x = stack2.pop();
list.add(x.val);
if(x.right!=null)
{
stack1.add(x.right);
}
if(x.left!=null)
{
stack1.add(x.left);
}
}
}
alist.add(list);
}
return alist;
}
public static void main(String[] args)
{
BineryTree a = new BineryTree(8);
BineryTree b = new BineryTree(6);
BineryTree c = new BineryTree(10);
BineryTree d = new BineryTree(5);
BineryTree e = new BineryTree(7);
BineryTree f = new BineryTree(9);
BineryTree g = new BineryTree(11);
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
ArrayList<ArrayList<Integer>> alist = BineryTreeToQueue(a);
for(int i=0;i<alist.size();i++)
{
for(int j=0;j<alist.get(i).size();j++)
{
System.out.print(alist.get(i).get(j)+" ");
}
System.out.println();
}
}
}