首页 > 代码库 > 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]]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Solution:

 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>> res = new ArrayList<List<Integer>>();13         List<Integer> oneRes = new ArrayList<Integer>();14         if (root==null){15             return res;16         }17 18         List<TreeNode> lastLevel = new ArrayList<TreeNode>();19         lastLevel.add(root);20         oneRes.add(root.val);21         res.add(oneRes);22         List<TreeNode> curLevel;23         while (lastLevel.size()!=0){24             oneRes = new ArrayList<Integer>();25             curLevel = new ArrayList<TreeNode>();26             for (int i=0;i<lastLevel.size();i++){27                 TreeNode curNode = lastLevel.get(i);28                 if (curNode.left!=null){29                     curLevel.add(curNode.left);30                     oneRes.add(curNode.left.val);31                 }32                 if (curNode.right!=null){33                     curLevel.add(curNode.right);34                     oneRes.add(curNode.right.val);35                 }36             }37             if (curLevel.size()==0){38                 break;39             } else {40                 res.add(oneRes);41                 lastLevel = curLevel;42             }43         }44 45         return res;        46     }47 }

 

Leetcode-Binary Tree Level Order Traversal