102. Order level traversal

102_solution1_iterative.c

#include "tree_node.h"
#include <stdlib.h>

#define MAX_NODES 2000 // constraint: number of nodes is in [0, 2000]

// returns an array of levels; sets *returnSize to the level count and
// (*returnColumnSizes)[i] to the size of level i
int **levelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes) {
  *returnSize = 0;
  *returnColumnSizes = malloc(MAX_NODES * sizeof(int));
  int **res = malloc(MAX_NODES * sizeof(int *));
  if (!root)
    return res;

  struct TreeNode **queue = malloc(MAX_NODES * sizeof(struct TreeNode *));
  int head = 0, tail = 0;
  queue[tail++] = root;

  while (head < tail) {
    int sz = tail - head;
    int *cur = malloc(sz * sizeof(int));

    for (int i = 0; i < sz; i++) {
      struct TreeNode *node = queue[head++];

      cur[i] = node->val;
      if (node->left)
        queue[tail++] = node->left;
      if (node->right)
        queue[tail++] = node->right;
    }

    (*returnColumnSizes)[*returnSize] = sz;
    res[(*returnSize)++] = cur;
  }

  free(queue);
  return res;
}

102_solution2_recursive.c

#include "tree_node.h"
#include <stdlib.h>

#define MAX_NODES 2000 // constraint: number of nodes is in [0, 2000]

static void dfs(struct TreeNode *node, int depth, int **res, int *sizes, int *levels) {
  if (!node)
    return;

  // first visit of a new depth: allocate its row
  if (depth == *levels) {
    res[depth] = malloc(MAX_NODES * sizeof(int));
    sizes[depth] = 0;
    (*levels)++;
  }

  res[depth][sizes[depth]++] = node->val;

  dfs(node->left, depth + 1, res, sizes, levels);
  dfs(node->right, depth + 1, res, sizes, levels);
}

// returns an array of levels; sets *returnSize to the level count and
// (*returnColumnSizes)[i] to the size of level i
int **levelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes) {
  int **res = malloc(MAX_NODES * sizeof(int *));
  *returnColumnSizes = malloc(MAX_NODES * sizeof(int));
  *returnSize = 0;

  dfs(root, 0, res, *returnColumnSizes, returnSize);
  return res;
}

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

102_solution1_iterative.cpp

#include "tree_node.h"
#include <queue>
#include <vector>

using namespace std;

vector<vector<int>> levelOrder(TreeNode *root) {
  vector<vector<int>> res;
  if (!root)
    return res;

  queue<TreeNode *> q;
  q.push(root);

  while (!q.empty()) {
    int sz = q.size();
    vector<int> cur;

    for (int i = 0; i < sz; i++) {
      TreeNode *node = q.front();
      q.pop();

      cur.push_back(node->val);
      if (node->left)
        q.push(node->left);
      if (node->right)
        q.push(node->right);
    }
    res.push_back(cur);
  }
  return res;
}

102_solution2_recursive.cpp

#include "tree_node.h"
#include <vector>

using namespace std;

class Solution {
public:
  vector<vector<int>> levelOrder(TreeNode *root) {
    vector<vector<int>> res;
    dfs(root, 0, res);
    return res;
  }

private:
  void dfs(TreeNode *node, int depth, vector<vector<int>> &res) {
    if (!node)
      return;

    // create vector for new depth
    if (depth == res.size())
      res.push_back({});

    res[depth].push_back(node->val);

    dfs(node->left, depth + 1, res);
    dfs(node->right, depth + 1, res);
  }
};

tree_node.h

#pragma once

// 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) {}
};

102_solution1_iterative.go

package trees

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }

    queue := []*TreeNode{root}

    for len(queue) > 0 {
        sz := len(queue)
        cur := make([]int, 0, sz)

        for _, node := range queue[:sz] {
            cur = append(cur, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        queue = queue[sz:]
        res = append(res, cur)
    }

    return res
}

102_solution2_recursive.go

package trees

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}

    var dfs func(node *TreeNode, depth int)
    dfs = func(node *TreeNode, depth int) {
        if node == nil {
            return
        }

        // create slice for new depth
        if depth == len(res) {
            res = append(res, []int{})
        }

        res[depth] = append(res[depth], node.Val)

        dfs(node.Left, depth+1)
        dfs(node.Right, depth+1)
    }

    dfs(root, 0)
    return res
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

102_solution1_iterative.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;

        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);

        while (!q.isEmpty()) {
            int sz = q.size();
            List<Integer> cur = new ArrayList<>();

            for (int i = 0; i < sz; i++) {
                TreeNode node = q.poll();

                cur.add(node.val);
                if (node.left != null)
                    q.add(node.left);
                if (node.right != null)
                    q.add(node.right);
            }
            res.add(cur);
        }
        return res;
    }
}

102_solution2_recursive.java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, 0, res);
        return res;
    }

    private void dfs(TreeNode node, int depth, List<List<Integer>> res) {
        if (node == null)
            return;

        // create list for new depth
        if (depth == res.size())
            res.add(new ArrayList<>());

        res.get(depth).add(node.val);

        dfs(node.left, depth + 1, res);
        dfs(node.right, depth + 1, res);
    }
}

TreeNode.java

// Definition for a binary tree node.
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;
    }
}

102_solution1_iterative.js

const TreeNode = require("./tree_node");

var levelOrder = function (root) {
  const res = [];
  if (!root) return res;

  // index-based queue: avoids the O(n) cost of Array.shift()
  const queue = [root];
  let head = 0;

  while (head < queue.length) {
    const sz = queue.length - head;
    const cur = [];

    for (let i = 0; i < sz; i++) {
      const node = queue[head++];

      cur.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(cur);
  }
  return res;
};

102_solution2_recursive.js

const TreeNode = require("./tree_node");

var levelOrder = function (root) {
  const res = [];

  const dfs = (node, depth) => {
    if (!node) return;

    // create array for new depth
    if (depth === res.length) res.push([]);

    res[depth].push(node.val);

    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  };

  dfs(root, 0);
  return res;
};

tree_node.js

// 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;
}

module.exports = TreeNode;

102_solution1_iterative.py

from collections import deque
from typing import List, Optional

from tree_node import TreeNode


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root:
            return res

        q = deque([root])

        while q:
            cur = []

            for _ in range(len(q)):
                node = q.popleft()

                cur.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(cur)
        return res

102_solution2_recursive.py

from typing import List, Optional

from tree_node import TreeNode


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if not node:
                return

            # create list for new depth
            if depth == len(res):
                res.append([])

            res[depth].append(node.val)

            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)

        dfs(root, 0)
        return res

tree_node.py

# 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

102_solution1_iterative.rs

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

use crate::tree_node::TreeNode;

impl Solution {
    pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let mut res = Vec::new();

        let mut q = VecDeque::new();
        if let Some(r) = root {
            q.push_back(r);
        }

        while !q.is_empty() {
            let mut cur = Vec::new();

            for _ in 0..q.len() {
                let node = q.pop_front().unwrap();
                let node = node.borrow();

                cur.push(node.val);
                if let Some(l) = &node.left {
                    q.push_back(Rc::clone(l));
                }
                if let Some(r) = &node.right {
                    q.push_back(Rc::clone(r));
                }
            }
            res.push(cur);
        }
        res
    }
}

102_solution2_recursive.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

type Link = Option<Rc<RefCell<TreeNode>>>;

impl Solution {
    pub fn level_order(root: Link) -> Vec<Vec<i32>> {
        let mut res = Vec::new();
        Self::dfs(&root, 0, &mut res);
        res
    }

    fn dfs(node: &Link, depth: usize, res: &mut Vec<Vec<i32>>) {
        if let Some(n) = node {
            let n = n.borrow();

            // create vec for new depth
            if depth == res.len() {
                res.push(Vec::new());
            }

            res[depth].push(n.val);

            Self::dfs(&n.left, depth + 1, res);
            Self::dfs(&n.right, depth + 1, res);
        }
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// 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,
        }
    }
}