JZ32 从上往下打印二叉树

JZ32 从上往下打印二叉树

好像最近做的稍微有几道了，脑子也慢慢灵光起来了。我竟然没看题解做出了一道题。二叉树这种东西空口算，还行，但是一写算法就会很头疼。尤其是他是典型的递归结构，我递归总是感觉理解的不太对味儿。最后在和递归缠斗了半天后，我就想到了一种非递归的方法

题目

不分行从上往下打印出二叉树的每个结点，同层结点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空结点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。

思路

我写代码的时候用到了两个链表，不过后来看题解，一个用队列会更优，不过那个优化起来很简单，先说我的思路。

想象一下你有两个链表。一个链表l1存放头结点，一个链表l2存放最终数据：

l1:头结点8进去啦

l2：快快告诉我值:8,l2:8
l1:在尾部加入头结点的左右结点l1:8,6,10
l1:已经把8吃干抹净了，踢出去l1:6,10

从左往右找树的结点，所以接下来应该找头结点的左结点也就是6
l2:快告诉我结点6的值：6，l2:8,2
l1:8的左右结点都有了，下来我想知道的是第三行的左边的值，也就是6的左右结点，空 l1:6,10
l1:已经把6吃干抹净了，踢出去
以此类推......

代码

package elevDay;

import java.util.ArrayList;

public class JZ32 {
	public ArrayList PrintFromTopToBottom(TreeNode root) {
        ArrayList l1 = new ArrayList();
        ArrayList l2 = new ArrayList();
      //如果头节点不为空
        if (root!=null) {
        	l1.add(root);
		}
        //若头结点列表不为空
        while(l1.size()>0) {
            //向l1添加新的头节点-原头节点的左右节点
            if (l1.get(0).left!=null) {
        		l1.add(l1.get(0).left);
			}
            if(l1.get(0).right!=null) {
            	l1.add(l1.get(0).right);
            }
            //d出的节点加入最终列表
            l2.add(l1.get(0).val);
            l1.remove(0);
        }
        return l2;
    }
	public static void main(String[] args) {
		TreeNode node1 = new TreeNode(8);
		TreeNode node2 = new TreeNode(6);
		TreeNode node3 = new TreeNode(10);
		TreeNode node4 = new TreeNode(2);
		TreeNode node5 = new TreeNode(1);
		node1.left = node2;
		node1.right = node3;
		node3.left = node4;
		node3.right = node5;
		JZ32 jz32 = new JZ32();
		jz32.PrintFromTopToBottom(node1);
	}

}