题目
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
思路 + 代码
其实就是二叉树层次遍历的变体。
遍历过程中,如果是二叉树的偶数层,就顺序遍历;否则逆序遍历。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| import java.util.ArrayList;
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); if(pRoot == null) return res; int layer = 0; int location = 0; queue.add(pRoot); while(!queue.isEmpty()){ int len = queue.size(); Integer[] nums = new Integer[len]; for(int i=0;i<len; ++i){ TreeNode tmp = queue.remove(); if(layer%2!=0) location = len-1-i; else location = i; nums[location]=tmp.val; if(tmp.left!=null) queue.add(tmp.left); if(tmp.right!=null) queue.add(tmp.right); } ArrayList<Integer> list = new ArrayList<Integer>(); Collections.addAll(list, nums); if(list.size()>0) res.add(list); layer++; } return res; } }
|