JavaArithmetic/src/LeetCode/LeetCode102.java at master · feinibuai/JavaArithmetic · GitHub

Repository navigation

History

package LeetCode;

import javafx.util.Pair;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

public class LeetCode102 {

/// 102. Binary Tree Level Order Traversal

/// https://leetcode.com/problems/binary-tree-level-order-traversal/description/

/// 二叉树的层序遍历

/// 时间复杂度: O(n), n为树的节点个数

/// 空间复杂度: O(n)

// Definition for a binary tree node.

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val = x; }

}

public List<List<Integer>> levelOrder(TreeNode root) {

ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();

if(root == null)

return res;

// 我们使用LinkedList来做为我们的先入先出的队列

LinkedList<Pair<TreeNode, Integer>> queue = new LinkedList<Pair<TreeNode, Integer>>();

queue.addLast(new Pair<TreeNode, Integer>(root, 0));

while(!queue.isEmpty()){

// 出列，拿到队列的TreeNode和level

Pair<TreeNode, Integer> front = queue.removeFirst();

TreeNode node = front.getKey();

int level = front.getValue();

// 如果level == res.size() --->新的一层--->new 出一个ArrayList()

if(level == res.size()) {

res.add(new ArrayList<Integer>());

}

assert level < res.size();

res.get(level).add(node.val);

if(node.left != null)

queue.addLast(new Pair<TreeNode, Integer>(node.left, level + 1));

if(node.right != null)

queue.addLast(new Pair<TreeNode, Integer>(node.right, level + 1));

}

return res;

}

JavaArithmetic/src/LeetCode/LeetCode102.java at master · feinibuai/JavaArithmetic · GitHub

Repository navigation

Expand file tree

Breadcrumbs

LeetCode102.java

Latest commit

History

Breadcrumbs

LeetCode102.java

File metadata and controls