二叉树的锯齿形层次遍历

2020-12-13

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]
通过次数82,729提交次数149,825

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

在java中使用双端队列，可以从头或者尾部取出或者加入元素，从而实现从前往后和从后往前遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayDeque<TreeNode> treeNodeQueue = new ArrayDeque<>();
        List<List<Integer>> resultList = new ArrayList<>();
        if (root != null) {
            treeNodeQueue.add(root);
        }
        boolean flag = false;
        while (!treeNodeQueue.isEmpty()) {
            List<Integer> res = new ArrayList<>();
            int num = treeNodeQueue.size();

            if (!flag) {//从左往右
                flag = !flag;
                for (int i = 0; i < num; i++) {

                    TreeNode node = treeNodeQueue.poll();
                    res.add(node.val);
                    //因为是从后往前遍历因此需要先把右子树加进去
                    if (node.left != null) {
                        treeNodeQueue.offer(node.left);
                    }
                    if (node.right != null) {
                        treeNodeQueue.offer(node.right);
                    }
                }


            } else {//从右往左
                flag = !flag;

                for (int i = 0; i < num; i++) {
                    TreeNode node = treeNodeQueue.removeLast();

                    res.add(node.val);
                    if (node.right != null) {
                        treeNodeQueue.addFirst(node.right);
                    }
                    if (node.left != null) {
                        treeNodeQueue.addFirst(node.left);
                    }

                }
            }
            
            resultList.add(res);

        }
        return resultList;
    }
}

使用一个空节点作为每一层遍历结束的标志

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<List<Integer>>();
    }

    List<List<Integer>> results = new ArrayList<List<Integer>>();

    // add the root element with a delimiter to kick off the BFS loop
    LinkedList<TreeNode> node_queue = new LinkedList<TreeNode>();
    node_queue.addLast(root);
    node_queue.addLast(null);//遇到空节点，结束本层遍历

    LinkedList<Integer> level_list = new LinkedList<Integer>();
    boolean is_order_left = true;

    while (node_queue.size() > 0) {//在遍历时不对TreeNode加入队列的顺序做修改，只是把遍历的结果插入结果列表的顺序进行了修改
      TreeNode curr_node = node_queue.pollFirst();
      if (curr_node != null) {//本层没有结束
        if (is_order_left)
          level_list.addLast(curr_node.val);
        else
          level_list.addFirst(curr_node.val);

        //以正常的顺序将节点加入队列
        if (curr_node.left != null)
          node_queue.addLast(curr_node.left);
        if (curr_node.right != null)
          node_queue.addLast(curr_node.right);

      } else {//遇到空节点，本层的遍历结束
        // we finish the scan of one level
        results.add(level_list);
        level_list = new LinkedList<Integer>();
        // prepare for the next level
        if (node_queue.size() > 0)
          node_queue.addLast(null);
        is_order_left = !is_order_left;//锯齿形的标志
      }
    }
    return results;
  }
}

时间复杂度和空间复杂度都是O(N)

深度优先遍历方式

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  protected void DFS(TreeNode node, int level, List<List<Integer>> results) {
    if (level >= results.size()) {//如果在当前的层还没有遍历过，也就是当前层的List的还没有初始化，初始化一个List
      LinkedList<Integer> newLevel = new LinkedList<Integer>();//每一层的列表
      newLevel.add(node.val);
      results.add(newLevel);//最终的结果列表
    } else {
      if (level % 2 == 0)
        results.get(level).add(node.val);//加到尾部
      else
        results.get(level).add(0, node.val);//加到头部
    }

    if (node.left != null) DFS(node.left, level + 1, results);//遍历左子树
    if (node.right != null) DFS(node.right, level + 1, results);//遍历右子树
  }

  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<List<Integer>>();
    }
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    DFS(root, 0, results);
    return results;
  }
}

时间复杂度O(N),空间复杂度O(H)，其中H是树的高度，包含N个节点的二叉树的高度大约为log（N）(以2为底)

参考文献

作者：LeetCode
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/solution/er-cha-shu-de-ju-chi-xing-ceng-ci-bian-li-by-leetc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。