LeetCode102-Binary-Tree-Level-Order-Traversal

痛定思痛。 2022-08-04 12:49 125阅读 0赞

**LeetCode 102 : 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.

OJ’s Binary Tree Serialization:  
The serialization of a binary tree follows a level order traversal, where ‘\#’ signifies a path terminator where no node exists below.

Here’s an example:  
 1  
 / \\  
2 3  
/  
4  
\\  
5  
The above binary tree is serialized as “\{1,2,3,\#,\#,4,\#,\#,5\}”.

来源： [https://leetcode.com/problems/binary-tree-level-order-traversal/][https_leetcode.com_problems_binary-tree-level-order-traversal]

**问题描述：**  
这道题其实就是将一颗二叉树按层次遍历将从上到下分别将每一层的节点的值从左到右保存在一个List中，然后将所有层的List再保存在一个List中。

我的解题代码如下：

/**
     * 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>> al = new ArrayList<List<Integer>>();
            List<Integer> nodeValues = new ArrayList<Integer>();
            if(root == null)
                return al;
    
            LinkedList<TreeNode> current = new LinkedList<TreeNode>();
            LinkedList<TreeNode> next = new LinkedList<TreeNode>();
            current.add(root);
    
            while(!current.isEmpty()){
                TreeNode node = current.remove();
    
                if(node.left != null)
                    next.add(node.left);
                if(node.right != null)
                    next.add(node.right);
    
                nodeValues.add(node.val);
                if(current.isEmpty()){
                    current = next;
                    next = new LinkedList<TreeNode>();
                    al.add(nodeValues);
                    nodeValues = new ArrayList();
                }
    
            }
            return al;
        }
    }

[https_leetcode.com_problems_binary-tree-level-order-traversal]: https://leetcode.com/problems/binary-tree-level-order-traversal/