You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

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

. 1 min read

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

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

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

Example:

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

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

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

Solutions

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

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

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)

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