Probléma
Adott egy bináris fa, tervezzen egy algoritmust, amely minden mélységben létrehoz egy linkelt listát az összes csomópontról (pl. ha van egy D mélységű fa, akkor D csatolt listája lesz).
Megoldás
Bár első pillantásra azt gondolhatnánk, hogy ez a probléma szintről-szintre történő bejárást igényel, ez valójában nem szükséges. Bármilyen módon bejárhatjuk a grafikont, feltéve, hogy közben tudjuk, hogy melyik szinten vagyunk.
Megvalósíthatjuk az előrendelési bejárási algoritmus egy egyszerű módosítását, ahol szintet lépünk át. + 1 a következő rekurzív híváshoz. Az alábbi kód egy mélységi keresést használó megvalósítást biztosít.
void createLevelLinkedList(TreeNode root, ArrayList<LinkedList<TreeNode>> lists, int level) { if (root == null) return; // base case LinkedList<TreeNode> list = null; if (lists.size() == level) { // Level not contained in list list = new LinkedList<TreeNode>(); /* Levels are always traversed in order. So., if this is the * first time we've visited level i, we must have seen levels * 0 through i - 1. We can therefore safely add the level at * the end. */ lists.add(list); } else { list = lists.get(level); } list.add(root); createLevelLinkedList(root.left, lists, level + 1); createLevelLinkedList(root.right, lists, level + 1); } ArrayList<LinkedList<TreeNode>> createLevelLinkedList( TreeNode root) { ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>(); createLevelLinkedList(root, lists, 0); return lists; }