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},

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;

        }

}

巴特西

Binary Tree Level Order Traversal java实现

最新文章

热门文章