首页 > 代码库 > [Leetcode] Binary Tree Level Order Traversal
[Leetcode] Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes‘ values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3 / 9 20 / 15 7
return its level order traversal as:
[ [3], [9,20], [15,7]]
Solution 1: BFS
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public List<List<Integer>> levelOrder(TreeNode root) {12 List<List<Integer>> ret=new ArrayList<List<Integer>>();13 if(root==null)14 return ret;15 16 Queue<TreeNode> queue=new LinkedList<TreeNode>();17 List<Integer> al=new ArrayList<Integer>();18 19 queue.add(root);20 int curLvl=1;21 int nexLvl=0;22 23 while(!queue.isEmpty()){24 TreeNode cur=queue.remove();25 al.add(cur.val);26 curLvl--;27 28 if(cur.left!=null){29 queue.add(cur.left);30 nexLvl++;31 }32 if(cur.right!=null){33 queue.add(cur.right);34 nexLvl++;35 }36 if(curLvl==0){37 ret.add(al);38 al=new ArrayList<Integer>();39 curLvl=nexLvl;40 nexLvl=0;41 }42 }43 44 return ret;45 }46 }
Solution 2: DFS
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 12 List<List<Integer>> ret;13 14 public List<List<Integer>> levelOrder(TreeNode root) {15 ret = new ArrayList<List<Integer>>();16 goDeeper(0, root);17 return ret;18 }19 20 private void goDeeper(int level, TreeNode root) {21 // TODO Auto-generated method stub22 if (root == null)23 return;24 if (ret.size() > level) {25 List<Integer> a = ret.get(level);26 a.add(root.val);27 } else {28 List<Integer> a = new LinkedList<Integer>();29 a.add(root.val);30 ret.add(a);31 }32 goDeeper(level+1, root.left);33 goDeeper(level+1, root.right);34 }35 }
[Leetcode] Binary Tree Level Order Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。