Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
May 20, 2021 07:58 am GMT

Solution: Binary Tree Level Order Traversal

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #102 (Medium): Binary Tree Level Order Traversal

Description:


(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Examples:

Example 1:
Input:root = [3,9,20,null,null,15,7]
Output:[[3],[9,20],[15,7]]
Visual:Example 1 Visual
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].
  • -1000 <= Node.val <= 1000

Idea:


(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

A binary tree level order traversal generally recommends a breadth first search (BFS) approach with the use of a queue data structure. When we process a node (curr), we'll push the node's children onto the end of the queue in the order in which we want to traverse (in this case, left to right). In this way, we'll have finished putting the next row in the queue at the same time we finish iterating through this row.

To help us keep track of the rows, we just nest the main loop inside another loop. At the beginning of the outer loop, we capture the queue length, which will tell us how long the row is. Then we can iterate through that many nodes, popping them off the queue's front one at a time, then process any end-of-row instructions. In the case of this problem, that will mean pushing the current row array (row) onto our answer array (ans).

We'll continue this process until the queue is empty, at which point we will have reached the end of the binary tree, and can return ans.

  • Time Complexity: O(N) where N is the number of nodes in the binary tree
  • Space Complexity: O(N) for our answer array

Javascript Code:


(Jump to: Problem Description || Solution Idea)

var levelOrder = function(root) {    let q = [root], ans = []    while (q[0]) {        let qlen = q.length, row = []        for (let i = 0; i < qlen; i++) {            let curr = q.shift()            row.push(curr.val)            if (curr.left) q.push(curr.left)            if (curr.right) q.push(curr.right)        }        ans.push(row)                }    return ans};

Python Code:


(Jump to: Problem Description || Solution Idea)

class Solution:    def levelOrder(self, root: TreeNode) -> List[List[int]]:        queue, ans = deque([root] if root else []), []        while len(queue):            qlen, row = len(queue), []            for _ in range(qlen):                curr = queue.popleft()                row.append(curr.val)                if curr.left: queue.append(curr.left)                if curr.right: queue.append(curr.right)            ans.append(row)        return ans

Java Code:


(Jump to: Problem Description || Solution Idea)

class Solution {    public List<List<Integer>> levelOrder(TreeNode root) {        List<List<Integer>> ans = new ArrayList<>();        if (root == null) return ans;        Deque<TreeNode> queue = new ArrayDeque<>();        queue.add(root);        while (!queue.isEmpty()) {            int qlen = queue.size();            List<Integer> row = new ArrayList<>();            for (int i = 0; i < qlen; i++) {                TreeNode curr = queue.poll();                row.add(curr.val);                if (curr.left != null) queue.add(curr.left);                if (curr.right != null) queue.add(curr.right);            }            ans.add(row);        }        return ans;    }}

C++ Code:


(Jump to: Problem Description || Solution Idea)

class Solution {public:    vector<vector<int>> levelOrder(TreeNode* root) {        vector<vector<int>> ans;        if (!root) return ans;        deque<TreeNode*> queue;        queue.push_back(root);        while (!queue.empty()) {            int qlen = queue.size();            vector<int> row;            for (int i = 0; i < qlen; i++) {                TreeNode* curr = queue.front();                queue.pop_front();                row.push_back(curr->val);                if (curr->left) queue.push_back(curr->left);                if (curr->right) queue.push_back(curr->right);            }            ans.push_back(row);        }        return ans;    }};

Original Link: https://dev.to/seanpgallivan/solution-binary-tree-level-order-traversal-36cg

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To