题目:

103. 二叉树的锯齿形层次遍历

题解:

1. 迭代法:

使用bfs,对应层判断一下奇偶,决定在表头还是表尾添加元素就可以了。

2. 递归法:

使用递归解法的时候(dfs),根据层数是奇数还是偶数,来判断添加到开头还是添加到末尾。

代码:

1. 迭代法:


/** * code103 */

import java.util.*;

public class code103 {

    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int count = 0;
        while (!queue.isEmpty()) {
            count++;
            int size = queue.size();
            List<Integer> tmp = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                TreeNode t = queue.poll();
                tmp.add(t.val);
                if (t.left != null) {
                    queue.offer(t.left);
                }
                if (t.right != null) {
                    queue.offer(t.right);
                }
            }
            if (count % 2 == 1) {
                res.add(tmp);
            } else if (count % 2 == 0) {
                Collections.reverse(tmp);
                res.add(tmp);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println("***************************************");
        Integer nums[] = { 3, 9, 20, null, null, 15, 7 };
        TreeNode tree = ConstructTree.constructTree(nums);
        TreeOperation.show(tree);
        System.out.println("***************************************");
        List<List<Integer>> res = zigzagLevelOrder(tree);
        System.out.println(res.toString());
        System.out.println("***************************************");
    }
}

2. 递归法:


/** * code103 */

import java.util.*;

public class code103 {

    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> res = new ArrayList<>();
        dfs(1, root, res);
        return res;
    }

    public static void dfs(int index, TreeNode root, List<List<Integer>> res) {
        if (res.size() < index) {
            res.add(new ArrayList<Integer>());
        }
        if (index % 2 == 1) {
            res.get(index - 1).add(root.val);
        } else if (index % 2 == 0) {
            res.get(index - 1).add(0, root.val);
        }

        if (root.left != null) {
            dfs(index + 1, root.left, res);
        }
        if (root.right != null) {
            dfs(index + 1, root.right, res);
        }
    }

    public static void main(String[] args) {
        System.out.println("***************************************");
        Integer nums[] = { 3, 9, 20, null, null, 15, 7 };
        TreeNode tree = ConstructTree.constructTree(nums);
        TreeOperation.show(tree);
        System.out.println("***************************************");
        List<List<Integer>> res = zigzagLevelOrder(tree);
        System.out.println(res.toString());
        System.out.println("***************************************");
    }
}

参考:

  1. python,java实现锯齿遍历
  2. Java双栈交替遍历
  3. 交替使用栈简单实现锯齿形层次遍历
  4. java 我这个超级好理解,但是也比较简单的思路,击败99%
  5. 递归和非递归两种解法
  6. 迭代和递归
  7. 层序遍历变种,用flag来切换不同层的顺序,达到锯齿效果。
  8. 1ms 简洁Java 没有reverse哦 击败99.83% 带清晰注释