描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

思路1：队列层序遍历

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if(pRoot == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        while(!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            // 记录当前队列长度
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                //奇数层插入头部
                if(ret.size() % 2 == 1) {
                    list.add(0, node.val);
                } else {
                    list.add(node.val);
                }
            }
            ret.add(list);
        }
        return ret;
    }
}

每次循环都要计算当前是奇数层还是偶数层。

优化1：使用flag标记，不断取反

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if(pRoot == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        boolean addHead = false;
        while(!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                if(addHead) {
                    list.add(0, node.val);
                } else {
                    list.add(node.val);
                }
            }
            ret.add(list);
            addHead = !addHead;
        }
        return ret;
    }
}

ArrayList每次插入头部，都需要拷贝数组，效率较低

优化2：遍历完之后再统一对列表进行反转

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if(pRoot == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        boolean addHead = false;
        while(!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                list.add(node.val);
            }
            if(addHead) {
                Collections.reverse(list);
            }
            ret.add(list);
            addHead = !addHead;
        }
        return ret;
    }
}

思路2：使用双端队列

    1
   2、3
4、5、6、7

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if(pRoot == null) {
            return ret;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(pRoot);
        while(!deque.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            // 奇数层，从头开始取，新元素加入尾部
            for(int i = deque.size(); i > 0; i--) {
                TreeNode node = deque.removeFirst();
                // 先取出左节点
                if(node.left != null) {
                    deque.addLast(node.left);
                }
                if(node.right != null) {
                    deque.addLast(node.right);
                }
                list.add(node.val);
            }
            ret.add(list);
            if(deque.isEmpty()) {
                break;
            }
            // 偶数层，从尾部取出，新元素加入头部
            list = new ArrayList<>();
            for(int i = deque.size(); i > 0; i--) {
                TreeNode node = deque.removeLast();
                // 先取出右节点
                if(node.right != null) {
                    deque.addFirst(node.right);
                }
                if(node.left != null) {
                    deque.addFirst(node.left);
                }
                list.add(node.val);
            }
            ret.add(list);
        }
        return ret;
    }
}

思路3：递归

递归记录当前层数，存入对应的列表中

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        dfs(0, pRoot);
        return ret;
    }
    ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    void dfs(int level, TreeNode node) {
        if(node == null) {
            return;
        }
        if(ret.size() == level) {
            ret.add(new ArrayList<>());
        }
        if(level % 2 == 1) {
            ret.get(level).add(0, node.val);
        } else {
            ret.get(level).add(node.val);
        }
        dfs(level + 1, node.left);
        dfs(level + 1, node.right);
    }
}