Java solution by both Recursion and iteration


  • 0
    X
    // Recursion
    private void help(List<List<Integer>> rst, TreeNode root, int level) {
        if (root == null) return;
        if (rst.size() == level) rst.add(new LinkedList<Integer>());
        if (level % 2 == 0) rst.get(level).add(root.val);
        else rst.get(level).add(0, root.val);
        help(rst, root.left, level + 1);
        help(rst, root.right, level + 1);
    }
    
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    	List<List<Integer>> rst = new ArrayList<List<Integer>>();
    	help(rst, root, 0);
    	return rst;
    }
    
    // Iteration
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
    	if (root == null) return rst;
    	Queue<TreeNode> q = new LinkedList<TreeNode>();
    	q.offer(root);
    	int depth = 0;
    	while (!q.isEmpty()) {
    		int level = q.size();
    		List<Integer> cur = new LinkedList<Integer>();
    		for (int i = 0; i < level; i++) {
    			TreeNode temp = q.poll();
    			if (depth % 2 == 0) cur.add(temp.val);
    			else cur.add(0, temp.val);
    			if (temp.left != null) q.offer(temp.left);
    			if (temp.right != null) q.offer(temp.right);
    		}
    		rst.add(cur);
    		depth++;
    	}
    	return rst;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.