103. Binary Tree Zigzag Level Order Traversal

Description

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Solutions

Solution 1: BFS

To implement zigzag level order traversal, we need to add a flag left on the basis of level order traversal. This flag is used to mark the order of the node values in the current level. If left is true, the node values of the current level are stored in the result array ans from left to right. If left is false, the node values of the current level are stored in the result array ans from right to left.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        boolean left = true;
        while (!q.isEmpty()) {
            List<Integer> t = new ArrayList<>();
            for (int n = q.size(); n > 0; --n) {
                TreeNode node = q.poll();
                t.add(node.val);
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
            if (!left) {
                Collections.reverse(t);
            }
            ans.add(t);
            left = !left;
        }
        return ans;
    }
}

//////

public class Binary_Tree_Zigzag_Level_Order_Traversal {

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */

    // count as level marker
    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

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

            if (root == null) {
                return result;
            }

            boolean isLeftToRight = true;

            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);

            int currentLevelCount = 1;
            int nextLevelCount = 0;

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

            while (!q.isEmpty()) {
                TreeNode current = q.poll();
                currentLevelCount--;

                if (isLeftToRight) {
                    one.add(current.val);
                } else {
                    one.add(0, current.val);
                }

                if (current.left != null) {
                    q.offer(current.left);
                    nextLevelCount++;
                }
                if (current.right != null) {
                    q.offer(current.right);
                    nextLevelCount++;
                }

                if (currentLevelCount == 0) {
                    currentLevelCount = nextLevelCount;
                    nextLevelCount = 0;

                    result.add(one);
                    one = new ArrayList<>();

                    isLeftToRight = !isLeftToRight;
                }
            }

            return result;
        }
    }

    public class Solution_nullAsMarker {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

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

            if (root == null) {
                return list;
            }

            Queue<TreeNode> q = new LinkedList<>();

            q.offer(root);
            q.offer(null);// @note: use null as marker for end of level

            boolean direction = true; // true: left=>right, false: right=>left
            List<Integer> oneLevel = new ArrayList<>();
            while (!q.isEmpty()) {

                TreeNode current = q.poll();

                if (current == null) {
                    List<Integer> copy = new ArrayList<>(oneLevel);
                    list.add(copy);

                    // clean after one level recorded
                    oneLevel.clear();// @memorize: this api
                    direction = !direction;

                    // @note:@memorize: if stack is now empty then DO NOT add null, or else infinite looping
                    // sk.offer(null); // add marker
                    if (!q.isEmpty()) {
                        q.offer(null); // add marker
                    }

                    continue;
                }

                if (direction) {
                    oneLevel.add(current.val);
                } else {
                    oneLevel.add(0, current.val);
                }

                // @note:@memorize: since using null as marker, then must avoid adding null when children are null
                // sk.offer(current.left);
                // sk.offer(current.right);
                if (current.left != null) {
                    q.offer(current.left);
                }
                if (current.right != null) {
                    q.offer(current.right);
                }

            }

            return list;
        }
    }

}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        queue<TreeNode*> q{ {root} };
        int left = 1;
        while (!q.empty()) {
            vector<int> t;
            for (int n = q.size(); n; --n) {
                auto node = q.front();
                q.pop();
                t.emplace_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (!left) reverse(t.begin(), t.end());
            ans.emplace_back(t);
            left ^= 1;
        }
        return ans;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

'''
can also use list.insert()

>>> my_list = [2, 3, 4]
>>> my_list.insert(0, 1)  # Insert 1 at the head of the list
>>> print(my_list)  # Output: [1, 2, 3, 4]


>>> a = deque([])
>>> a
deque([])
>>> a.append(1)
>>> a.append(2)
>>> a.append(3)
>>> a
deque([1, 2, 3])
>>>
>>> a.append(0, 555)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: deque.append() takes exactly one argument (2 given)
>>> a.insert(0, 555)
>>> a
deque([555, 1, 2, 3])
'''

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        if root is None:
            return ans
        q = deque([root])
        ans = []
        left = True
        while q:
            t = []
            for _ in range(len(q)):
                node = q.popleft()
                t.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(t if left else t[::-1])
            left = (not left)
        return ans

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque


class Solution(object):
  def zigzagLevelOrder(self, root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """
    stack = deque([root])
    ans = []
    odd = True
    while stack:
      level = []
      for k in range(0, len(stack)):
        top = stack.popleft()
        if top is None:
          continue
        level.append(top.val)
        stack.append(top.left)
        stack.append(top.right)
      if level:
        if odd:
          ans.append(level)
        else:
          ans.append(level[::-1])
      odd = not odd
    return ans

############

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        if root is None:
            return ans
        q = deque([root])
        ans = []
        left = 1
        while q:
            t = []
            for _ in range(len(q)):
                node = q.popleft()
                t.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(t if left else t[::-1])
            left ^= 1
        return ans

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) (ans [][]int) {
	if root == nil {
		return
	}
	q := []*TreeNode{root}
	left := true
	for len(q) > 0 {
		t := []int{}
		for n := len(q); n > 0; n-- {
			node := q[0]
			q = q[1:]
			t = append(t, node.Val)
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		if !left {
			for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
				t[i], t[j] = t[j], t[i]
			}
		}
		ans = append(ans, t)
		left = !left
	}
	return
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function zigzagLevelOrder(root: TreeNode | null): number[][] {
    const res = [];
    if (root == null) {
        return res;
    }
    let isDesc = false;
    const queue = [root];
    while (queue.length !== 0) {
        const arr = queue.slice().map(() => {
            const { val, left, right } = queue.shift();
            left && queue.push(left);
            right && queue.push(right);
            return val;
        });
        res.push(isDesc ? arr.reverse() : arr);
        isDesc = !isDesc;
    }
    return res;
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function (root) {
    const ans = [];
    if (!root) {
        return ans;
    }
    const q = [root];
    let left = 1;
    while (q.length) {
        const t = [];
        for (let n = q.length; n; --n) {
            const node = q.shift();
            t.push(node.val);
            if (node.left) {
                q.push(node.left);
            }
            if (node.right) {
                q.push(node.right);
            }
        }
        if (!left) {
            t.reverse();
        }
        ans.push(t);
        left ^= 1;
    }
    return ans;
};

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn zigzag_level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        if root.is_none() {
            return res;
        }
        let mut is_desc = false;
        let mut q = VecDeque::new();
        q.push_back(root);
        while !q.is_empty() {
            let mut arr = vec![];
            for _ in 0..q.len() {
                if let Some(node) = q.pop_front().unwrap() {
                    let mut node = node.borrow_mut();
                    arr.push(node.val);
                    if node.left.is_some() {
                        q.push_back(node.left.take());
                    }
                    if node.right.is_some() {
                        q.push_back(node.right.take());
                    }
                }
            }
            if is_desc {
                arr.reverse();
            }
            is_desc = !is_desc;
            res.push(arr);
        }
        res
    }
}

103 - Binary Tree Zigzag Level Order Traversal

103. Binary Tree Zigzag Level Order Traversal

Description

Solutions

All Problems

All Solutions

Welcome to Subscribe On Youtube

103. Binary Tree Zigzag Level Order Traversal

Description

Solutions

All Problems

All Solutions