title: 算法小练——二叉树的层次遍历
date: 2019-11-21 22:06:50
categories:

• Algorithms
  tags:
• easy

二叉树的层次遍历

描述

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

示例

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

    3
   / \
  9  20
      /  \
    15   7

返回其层次遍历结果：

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

代码

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
   List<List<Integer>> levels = new ArrayList<>();  
	 public List<List<Integer>> levelOrder(TreeNode root) {
		 if(root==null) {
			 return levels;
		 }
	      helper(root,0);
	      
	      return levels;
     }
	 public void helper(TreeNode node,int level) {
 		 
 		 if(levels.size()==level) {
 			 levels.add(new ArrayList<Integer>());
 		 }
         //将同一层次的节点存储到同一个数组中的操作
 		 levels.get(level).add(node.val);
 		 if(node.left!=null) {
 			 helper(node.left,level+1);
 		 }
 		 if(node.right!=null) {
 			 helper(node.right,level+1);
 		 }
 	 }
}

笔记

递归的难度主要是如何保证将同一层的节点存储到同一个数组中去，这个算法中，利用了ArrayList有序的特性，并通过get方法与add方法来实现了，定位存储。