巨硬家面试题:二叉树的锯齿形层次遍历

给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行)

在线做题地址→

样例 1:

输入:{1,2,3}
输出:[[1],[3,2]]
解释:
    1
   / \\
  2   3
它将被序列化为 {1,2,3}

样例 2:

输入:{3,9,20,#,#,15,7}
输出:[[3],[20,9],[15,7]]
解释:
    3
   / \\
  9  20
    /  \\
   15   7
它将被序列化为 {3,9,20,#,#,15,7}

[题解]

算法:树的层次遍历

层次遍历,可以运用广度遍历的思想实现从上往下的逐层遍历。从头结点开始逐层遍历,开辟一个新队列,让头结点入队并计算此时的长度,每次都将当前层的子节点全部压入队列,然后对下一层的节点进行遍历,再将下一层的子节点压入队列,不断循环,一直遍历到底层,判断的终止条件就是队列不为空。

  • 循环里面,队列头出队,判断其是否有左右子结点,如果有,则将此点的子节点入队,但此时还不需要更新队列的长度,当前队列的长度是每层的长度。当这层的长度减为 0 时,就说明这层的遍历结束,开始更新长度为下一层的长度。
  • 出队的元素的值按照一层层压入结果数组
  • 因为题目锯齿形遍历
  • 我们用一个 isforward 标记当前方向,每遍历完一层,如果是反向的,则将这层的节点数组倒序,然后将这层的集合压入结果

复杂度分析

时间复杂度 O(n)

n 为节点数量

空间复杂度 O(n)

存下所有点的信息 n 为节点数量

 public class Solution
{
    /**
     * @param root: A Tree
     * @return: A list of lists of integer include the zigzag level order traversal of its nodes\' values.
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root){
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        //正反向标志
        boolean isForward = true;
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> subList = new ArrayList<Integer>();
            for (int i = 0 ; i < size ; i++) {
                TreeNode treeNode = q.poll();
                subList.add(treeNode.val);
                if (treeNode.left != null) { 
                    q.offer(treeNode.left);
                }
                if (treeNode.right != null) {
                    q.offer(treeNode.right);
                }
            }
            //根据标志来确认当前层遍历的方向
            if (!isForward) {
                Collections.reverse(subList);//翻转
            }
            ans.add(subList);
            //方向反转
            isForward = !isForward;
        }
        return ans;
    }
}

更多题解参见

Click to rate this post!
[Total: 0 Average: 0]

相关文章

One thought on “巨硬家面试题:二叉树的锯齿形层次遍历

发表回复

您的电子邮箱地址不会被公开。