【試題描述】定義一個函數，給定二叉樹，給每層生成一個鏈表

We can do a simple level by level traversal of the tree, with a slight modification of the breath-first traversal of the tree
In a usual breath first search traversal, we simply traverse the nodes without caring which level we are on In this case, it is critical to know the level We thus use a dummy node to indicate when we have finished one level and are starting on the next

【參考代碼】

1 public static ArrayList<LinkedList<Node>> findLevelLinkList(Node root) 2 { 3 int level = 0; 4 ArrayList<LinkedList<Node>> result = 5 new ArrayList<LinkedList<Node>>(); 6 LinkedList<Node> list = new LinkedList<Node>(); 7 8 list.add(root); 9 result.add(level, list); 10 11 while(true) 12 { 13 list = new LinkedList<Node>(); 14 for(int i=0;i< result.get(level).size();i++) 15 { 16 Node n = result.get(level).get(i); 17 if(n!=null) 18 { 19 if(n.left!=null) 20 list.add(n.left); 21 if(n.right!=null) 22 list.add(n.right); 23 } 24 } 25 if(list.size() >0) 26 result.add(level+1, list); 27 else 28 break; 29 level++; 30 } 31 return result; 32 }

?

總結

以上是生活随笔為你收集整理的【IT笔试面试题整理】给定二叉树，给每层生成一个链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。