题目:

LeetCode Premium Subscription
Problems
Pick One
Mock
Articles
Discuss
Book
fengsehng
102. Binary Tree Level Order Traversal My Submissions QuestionEditorial Solution
Total Accepted: 98313 Total Submissions: 302608 Difficulty: Easy
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]
]

题意:

  • 题意是把一颗二叉树,按照从上到下,,把每一排节点从左到右存进list,最后把所有list存进一个list
  • 考虑用递归,设置两个Queue,first和second来存放TreeNode。first来存放当前最下层的一行,second用来存放下一行,first的元素的左右节点赋值给second,把second的元素给first,往下移动
  • 考虑first是空的时候,停止,注意判断临时数组tmp是否为空,非空才能存进
  • -

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> all = new ArrayList<List<Integer>>();
        Queue<TreeNode> first = new LinkedList<TreeNode>();
        Queue<TreeNode> second = new LinkedList<TreeNode>();
        if(root == null){
            return all;
        }
        List<Integer> tmp = new ArrayList<Integer>();
        tmp.add(root.val);
        all.add(tmp);
        first.add(root);
        while(!first.isEmpty()){
            TreeNode node = first.poll();
            if(node.left != null){
                second.add(node.left);
            }
            if(node.right != null){
                second.add(node.right);
            }
            if(first.isEmpty()){
                List<Integer> tmp1 = new ArrayList<Integer>();
                while(!second.isEmpty()){
                    TreeNode n = second.poll();
                    first.add(n);
                    tmp1.add(n.val);
                }
                if(tmp1.size() != 0){
                    all.add(tmp1);
                }
                second.clear();
            }

        }
        return all;
    }
}
05-07 15:33