Advertisement
Guest User

binary tree level order traversal

a guest
Oct 22nd, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. class Solution {
  11. public List<List<Integer>> levelOrder(TreeNode root) {
  12. List<List<Integer>> lists = new ArrayList<List<Integer>>();
  13. if (root == null) return lists;
  14. Deque<TreeNode> queue1 = new ArrayDeque<TreeNode>();
  15. Deque<TreeNode> queue2 = new ArrayDeque<TreeNode>();
  16. queue1.offer(root);
  17. while (!queue1.isEmpty() || !queue2.isEmpty()){
  18. List<Integer> list = new ArrayList<Integer>();
  19. List<Integer> list2 = new ArrayList<Integer>();
  20.  
  21. while (!queue1.isEmpty()){
  22. TreeNode node = queue1.poll();
  23. list.add(node.val);
  24. if (node.left != null){
  25. queue2.offer(node.left);
  26. }
  27. if (node.right != null){
  28. queue2.offer(node.right);
  29. }
  30. }
  31.  
  32. if (!list.isEmpty()){
  33. lists.add(list);
  34. }
  35.  
  36. while (!queue2.isEmpty()){
  37. TreeNode node = queue2.poll();
  38. list2.add(node.val);
  39. if (node.left != null){
  40. queue1.offer(node.left);
  41. }
  42. if (node.right != null){
  43. queue1.offer(node.right);
  44. }
  45. }
  46.  
  47. if (!list2.isEmpty()){
  48. lists.add(list2);
  49. }
  50. }
  51. return lists;
  52. }
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement