Saturday, October 12, 2019

Leetcode solution 103: Binary Tree Zigzag Level Order Traversal

Problem Statement 

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

It’s purely an implementation problem to be honest. Very similar to to binary tree level order traversal, we just need to use some data structure to hold the values while we control the traversal order. I choose to use a deque (i.e., doubled linked list) to keep the order. You can also use a queue like many other online solutions but note when calling add(0, value) to an array list is not very efficient since to have array copy every time.

Solutions


Time Complexity: O(N) since we visit each node once
Space Complexity: O(N) since used a deque

References

No comments:

Post a Comment

Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!