1. 二叉树的层次遍历 - Binary Tree Level Order Traversal

102. 二叉树的层次遍历 - Binary Tree Level Order Traversal

【层次遍历-迭代】 【层次遍历-递归】

Problem Link

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

Example:

给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

Solution 【层次遍历-迭代】 ( 2ms)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new LinkedList<>();
        if(root == null)
            return result;
        queue.offer(root);
        TreeNode current, left, right;
        int size = 0;
        List<Integer> curList;
        while(queue.isEmpty() == false){
			size = queue.size();
			curList = new LinkedList<>();
			while(size != 0){
				current = queue.poll();
                size--;
				curList.add(current.val);
				left = current.left;
				right = current.right;
				if(left != null)
					queue.add(left);
				if(right != null)
					queue.add(right);
			}
			result.add(curList);
		}
        return result;
    }
}

Solution 【层次遍历-递归】 ( 0ms)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        function(root,list,0);
        return list;
    }
    
    public void function(TreeNode node,List<List<Integer>> list,int level){
        if(node == null)
            return;
        if(list.size()<=level)
            list.add(new ArrayList<Integer>());
        list.get(level).add(node.val);
        function(node.left,list,level+1);
        function(node.right,list,level+1);
    }
}

Notes