首页 > 代码库 > Binary Tree Level Order Traversal java实现

Binary Tree Level Order Traversal java实现

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]]

实现的关键在于定义两个标记位和队列:
1、标志位last和end。last为记录的是本层次的最后一个最后一个结点,end用于寻找下一层的最后一个结点。
2、队列是用于存储每个结点。
public class Solution {    public List<List<Integer>> levelOrder(TreeNode root) {            List<List<Integer>> list = new ArrayList<>();            List<Integer> lst = new ArrayList<>();            Queue<TreeNode> queue = new LinkedList<>();            queue.add(root);            TreeNode last =root;            TreeNode end = null;            while(!queue.isEmpty()){                TreeNode t = queue.remove();                if(t!=null){                    lst.add(t.val);                if(t.left != null){                    queue.add(t.left);                    end = t.left;                }                if(t.right != null){                    queue.add(t.right);                    end = t.right;                }                if(t == last ){                    list.add(lst);                    last =end;                    lst = new ArrayList<>();                }                }               }               return list;        }}