102. Binary Tree Level Order Traversal (Medium)

https://leetcode.com/problems/binary-tree-level-order-traversal/

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

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solutions

1.

class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();

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

        int maxDepth = maxDepth(root);

        // For different layer, allocate an ArrayList to hold the values.
        for (int i = 0; i < maxDepth; i++) {
            ans.add(new ArrayList<>());
        }

        recurse(root, 0, ans);

        return ans;
    }

    private int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left) + 1;
        int right = maxDepth(root.right) + 1;

        return Math.max(left, right);
    }

    private void recurse(TreeNode root, int depth, List<List<Integer>> ans) {
        if (root == null) {
            return;
        }

        // Apply pre-order visiting method such that values stored in each layer list
        // are arranged in the order from left to right.

        ans.get(depth).add(root.val);

        recurse(root.left, depth + 1, ans);
        recurse(root.right, depth + 1, ans);
    }
}

2.

class Solution {

    // How to define the border of each layer when applying BFS? Count the children nodes
    // when traverse the parent nodes.

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();

        // return answer of length 0 if root == null
        if (root == null) {
            return ans;
        }

        // Employ queue structure to BFS the tree
        Queue<TreeNode> queue = new ArrayDeque<>();

        // Insert the root of the tree to initialize the queue.
        queue.add(root);

        int count = 1;

        // Keep the elements visited by BFS order
        List<Integer> tmp = new ArrayList<>();

        // start BFS
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();

            int size = count;
            for (int i = 0; i < size; i++) {
                TreeNode parent = queue.poll();
                level.add(parent.val);
                count--;

                if (parent.left != null) {
                    queue.add(parent.left);
                    count++;
                }

                if (parent.right != null) {
                    queue.add(parent.right);
                    count++;
                }
            }

            ans.add(level);
        }

        // return answer.
        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-20 14:59:40

results matching ""

    No results matching ""