Leetcode #102 Binary Tree Level Order Traversal

Leetcode #102 Binary Tree Level Order Traversal

Difficulty: Medium

There's two ways to do this - iterative or recursive approach.

Iterative:

  • We will use a queue to keep track of the children's node of the existing level
  • Once we have iterate through the existing level, we reset the queue with it's children

Recursive:

  • We go by depth, for the 0th level, we can just insert the node value
  • If a depth doesn't exist yet, we will create a new level and initialize an array with the node's value
  • Otherwise, we can just push it if the arr[depth] already exist.

Link:Binary Tree Level Order Traversal

/**
 * 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 levelOrder = function(root) {
    let ans = [];

    let traverse = (node) => {
        let queue = []
        if(!node) return;

        if(node){
            queue.push(node);
        }

        while(queue.length >0){
            let level = []
            let newQueue = []
            let length = queue.length
            for(let n of queue){
                level.push(n.val)
                if(n.left){
                    newQueue.push(n.left)
                }
                if(n.right){
                    newQueue.push(n.right)
                }

            }
            queue = newQueue;
            ans.push(level)
        }
    }


    // Recursive style
    let recurse = (node, depth) => {
        if(!node) return;

        if(depth ==0){
            ans.push([node.val])
        }else if(ans[depth]){
            ans[depth].push(node.val)
        }else{
            console.log(depth)
            ans[depth] = [node.val]
        }

        recurse(node.left, depth+1)
        recurse(node.right, depth+1)
    }

    recurse(root, 0);

    return ans;
};

Did you find this article valuable?

Support Michelle Tan by becoming a sponsor. Any amount is appreciated!