Print all elements at a given level in the binary tree

原创转载请注明出处：http://agilestyle.iteye.com/blog/2360924

 

method 1 —— 使用两个队列

use a queue to store elements and levels

keep dequeing elements until the associated levels equals to the desired level

print out elements and stop when queue is empty

 

method 2 —— 递归

recursion

keep track of current level versus desired level

print out element when current = desired

 

package org.fool.java.test;

import java.util.LinkedList;
import java.util.Queue;

public class TreeLevelPrintTest {
    public static void main(String[] args) {
        //       4
        //    2     6
        //  1   3  5  7
        Tree myTree = new Tree(4);
        myTree.left = new Tree(2);
        myTree.right = new Tree(6);
        myTree.left.left = new Tree(1);
        myTree.left.right = new Tree(3);
        myTree.right.left = new Tree(5);
        myTree.right.right = new Tree(7);

        // use method 1
        printTreeLevel(myTree, 2);  // 1 3 5 7
        System.out.println();
        printTreeLevel(myTree, 1);  // 2 6
        System.out.println();
        printTreeLevel(myTree, 0);  // 4

        System.out.println();

        // use method 2
        printTreeLevel(myTree, 0, 2);
        System.out.println();
        printTreeLevel(myTree, 0, 1);
        System.out.println();
        printTreeLevel(myTree, 0, 0);
    }

    // method 1, use Queue
    private static void printTreeLevel(Tree t, int desire) {
        if (desire < 0) {
            return;
        }

        // now define 2 queues, one to store tree nodes, the other for current levels
        Queue<Tree> trees = new LinkedList<>();
        Queue<Integer> levels = new LinkedList<>();

        // start by pushing root node in the queue
        trees.add(t);
        levels.add(0);

        // now define a loop to continue while the queue is not empty
        while (!trees.isEmpty()) {
            Tree temp = trees.poll();
            int currentLevel = levels.poll();

            if (temp == null) {
                continue;
            } else if (currentLevel == desire) {
                System.out.print(temp.value + " ");
            } else {    // need to continue to its child tree nodes
                trees.add(temp.left);
                levels.add(currentLevel + 1);
                trees.add(temp.right);
                levels.add(currentLevel + 1);
            }
        }
    }

    // method 2, use recursion
    private static void printTreeLevel(Tree t, int currentLevel, int desire) {
        if(t == null || currentLevel > desire) {
            return;
        }

        if(currentLevel == desire) {
            System.out.print(t.value + " ");
        } else {
            // proceed to its left and right sub-trees
            printTreeLevel(t.left, currentLevel + 1, desire);
            printTreeLevel(t.right, currentLevel + 1, desire);
        }
    }

    private static class Tree {
        public int value;
        public Tree left;
        public Tree right;

        public Tree(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }
}

Console Output

 

Reference

https://www.youtube.com/watch?v=79fPL0F_1XA&index=43&list=PLlhDxqlV_-vkak9feCSrnjlrnzzzcopSG