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

 

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTreeLevelOrderTraversal {

    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     *
     * 二叉树按层次顺序遍历(广度优先遍历)
     */
    public class Solution {
        public LinkedList<LinkedList<Integer>> levelOrder(TreeNode root) {
            LinkedList<LinkedList<Integer>> l = new LinkedList<LinkedList<Integer>>();
            LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//用来存x层的节点
            LinkedList<TreeNode> childQueue = new LinkedList<TreeNode>();//用来存x层节点的孩子节点

            if (root == null ) return null;
            if (queue.isEmpty()) {//先把root节点放入队列中
                queue.add(root);
            }
            while (!queue.isEmpty()) {//队列不为空,那么排空queue队列,并把queue队列中节点的孩子存储在childQueue队列中
                LinkedList<Integer> t = new LinkedList<Integer>();//用来存储借点中获取的值

                while (!queue.isEmpty()) {
                    TreeNode n = queue.remove();
                    t.add(n.val);
                    if (n.left != null)
                        childQueue.add(n.left);
                    if (n.right != null)
                        childQueue.add(n.right);
                }
                l.add(t);//t加入到l中
                queue.clear();//清除queue队列
                queue = new LinkedList<TreeNode>(childQueue);//queue指向 用queue队列中节点的孩子组成的队列
                childQueue.clear();//孩子队列清空

            }
            return l;

        }
        }
}





Tagged on: , , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>