Reverse Level Order Traversal | GeeksforGeeks && LeetCode

Reverse Level Order Traversal | GeeksforGeeks

Example Tree

Reverse Level order traversal of the above tree is “4 5 2 3 1″.

METHOD 2 (Using Queue and Stack)
Key Point: Handle right node then left nodeThe idea is to use a stack to get the reverse level order. If we do normal level order traversal and instead of printing a node, push the node to a stack and then print contents of stack, we get “5 4 3 2 1″ for above example tree, but output should be “4 5 2 3 1″. So to get the correct sequence (left to right at every level), we process children of a node in reverse order, we first push the right subtree to stack, then left subtree.

void reverseLevelOrder(node* root)

{

    stack <node *> S;

    queue <node *> Q;

    Q.push(root);

    // Do something like normal level order traversal order. Following are the

    // differences with normal level order traversal

    // 1) Instead of printing a node, we push the node to stack

    // 2) Right subtree is visited before left subtree

    while (Q.empty() == false)

    {

        /* Dequeue node and make it root */

        root = Q.front();

        Q.pop();

        S.push(root);

        /* Enqueue right child */

        if (root->right)

            Q.push(root->right); // NOTE: RIGHT CHILD IS ENQUEUED BEFORE LEFT

        /* Enqueue left child */

        if (root->left)

            Q.push(root->left);

    }

    // Now pop all items from stack one by one and print them

    while (S.empty() == false)

    {

        root = S.top();

        cout << root->data << " ";

        S.pop();

    }

}

METHOD 1 (Recursive function to print a given level)
The only thing we need to change is, instead of calling printGivenLevel() from first level to last level, we call it from last level to first leve

void reverseLevelOrder(struct node* root)

{

    int h = height(root);

    int i;

    for (i=h; i>=1; i--) //THE ONLY LINE DIFFERENT FROM NORMAL LEVEL ORDER

        printGivenLevel(root, i);

}

/* Print nodes at a given level */

void printGivenLevel(struct node* root, int level)

{

    if (root == NULL)

        return;

    if (level == 1)

        printf("%d ", root->data);

    else if (level > 1)

    {

        printGivenLevel(root->left, level-1);

        printGivenLevel(root->right, level-1);

    }

}

LeetCode – Binary Tree Level Order Traversal II
http://blog.hfknight.com/?p=1249
// Solution, don’t need reverse array list public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> result = new ArrayList<List<Integer>>();// Use linkedlist levelOrderBottomHelper(root, result, 1); return result; } public void levelOrderBottomHelper(TreeNode root, List<List<Integer>> result, int depth) { if (root == null) return; List<Integer> list; if (result.size() < depth) { list = new ArrayList<Integer>(); result.add(0, list); } else { list = result.get(result.size() - depth); } list.add(root.val); levelOrderBottomHelper(root.left, result, depth+1); levelOrderBottomHelper(root.right, result, depth+1); }


http://www.programcreek.com/2014/04/leetcode-binary-tree-level-order-traversal-ii-java/

public List<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
    ArrayList<ArrayList<Integer>> result = new  ArrayList<ArrayList<Integer>>();
 
    if(root == null){
        return result;
    }
 
    LinkedList<TreeNode> current = new LinkedList<TreeNode>();
    LinkedList<TreeNode> next = new LinkedList<TreeNode>();
    current.offer(root);
 
    ArrayList<Integer> numberList = new ArrayList<Integer>();
 
    // need to track when each level starts
    while(!current.isEmpty()){
        TreeNode head = current.poll();
 
        numberList.add(head.val);
 
        if(head.left != null){
            next.offer(head.left);
        }
        if(head.right!= null){
            next.offer(head.right);
        }
 
        if(current.isEmpty()){
            current = next;
            next = new LinkedList<TreeNode>();
            result.add(numberList);
            numberList = new ArrayList<Integer>();
        }
    }
     //return Collections.reverse(result); // use this
    ArrayList<ArrayList<Integer>> reversedResult = new  ArrayList<ArrayList<Integer>>();
    for(int i=result.size()-1; i>=0; i--){
        reversedResult.add(result.get(i));
    }
 
    return reversedResult;
}

http://www.jyuan92.com/blog/leetcode_107-binary-tree-level-order-traversal-ii/
Actually, it’s not a good algorithm, because everytime when you add a value into the first index of ArrayList. All the element in the ArrayList will move to the next one. Which will make the Time Complexity to be O(n^2).
-- How about use LinkedList? http://www.acmerblog.com/leetcode-solution-binary-tree-level-order-traversal-ii-6348.html

public static ArrayList<ArrayList<Integer>> levelOrderButtom1(TreeNode root) {

        // write your code here

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

        if (root == null) {

            return list;

        }

        int currentCount = 1;

        int nextCount = 0;

 

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

        queue.offer(root);

 

        ArrayList<Integer> temp = new ArrayList<Integer>();

 

        while(!queue.isEmpty()) {

            TreeNode node = queue.poll();

            temp.add(node.val);

            currentCount--;

            if (node.left != null) {

                queue.offer(node.left);

                nextCount++;

            }

            if (node.right != null) {

                queue.offer(node.right);

                nextCount++;

            }

            if (currentCount == 0) {

                currentCount = nextCount;

                nextCount = 0;

                list.add(0, temp);

                temp = new ArrayList<Integer>();

            }

        }

        return list;

    }

http://bangbingsyb.blogspot.com/2014/11/leetcode-binary-tree-level-order.html
Read full article from Reverse Level Order Traversal | GeeksforGeeks