LEETCODE 102.二叉树的层次遍历

LEETCODE 102.二叉树的层次遍历

题目描述

给定一个二叉树,返回其按层次遍历的节点值。(即逐层地,从左到右访问所有节点)。
例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

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

题目地址:
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

迭代实现

广度优先遍历是按层层推进的方式,遍历每一层的节点。题目要求的是返回每一层的节点值,所以这题用广度优先来做非常合适。
广度优先需要用队列作为辅助结构,我们先将根节点放到队列中,然后不断遍历队列。

首先拿出根节点,如果左子树/右子树不为空,就将他们放入队列中。第一遍处理完后,根节点已经从队列中拿走了,而根节点的两个孩子已放入队列中了,现在队列中就有两个节点25

第二次处理,会将25这两个节点从队列中拿走,然后再将25的子节点放入队列中,现在队列中就有三个节点346

我们把每层遍历到的节点都放入到一个结果集中,最后返回这个结果集就可以了。
时间复杂度:O(n)
空间复杂度:O(n)
java代码:

import java.util.*;	
class Solution {
	public List<List<Integer>> levelOrder(TreeNode root) {
		if(root==null) {
			return new ArrayList<List<Integer>>();
		}
		
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		//将根节点放入队列中,然后不断遍历队列
		queue.add(root);
		while(queue.size()>0) {
			//获取当前队列的长度,这个长度相当于 当前这一层的节点个数
			int size = queue.size();
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			//将队列中的元素都拿出来(也就是获取这一层的节点),放到临时list中
			//如果节点的左/右子树不为空,也放入队列中
			for(int i=0;i<size;++i) {
				TreeNode t = queue.remove();
				tmp.add(t.val);
				if(t.left!=null) {
					queue.add(t.left);
				}
				if(t.right!=null) {
					queue.add(t.right);
				}
			}
			//将临时list加入最终返回结果中
			res.add(tmp);
		}
		return res;
	}
}
                                                                                          

python代码:

class Solution(object):
	def levelOrder(self, root):
		"""
		:type root: TreeNode
		:rtype: List[List[int]]
		"""
		if not root:
			return []
		res = []
		queue = [root]
		while queue:
			# 获取当前队列的长度,这个长度相当于 当前这一层的节点个数
			size = len(queue)
			tmp = []
			# 将队列中的元素都拿出来(也就是获取这一层的节点),放到临时list中
			# 如果节点的左/右子树不为空,也放入队列中
			for _ in xrange(size):
				r = queue.pop(0)
				tmp.append(r.val)
				if r.left:
					queue.append(r.left)
				if r.right:
					queue.append(r.right)
			# 将临时list加入最终返回结果中
			res.append(tmp)
		return res
                                                                                        

递归实现

用广度优先处理是很直观的,可以想象成是一把刀横着切割了每一层,但是深度优先遍历就不那么直观了。

我们开下脑洞,把这个二叉树的样子调整一下,摆成一个田字形的样子。田字形的每一层就对应一个list。

按照深度优先的处理顺序,会先访问节点1,再访问节点2,接着是节点3
之后是第二列的45,最后是第三列的6
每次递归的时候都需要带一个index(表示当前的层数),也就对应那个田字格子中的第几行,如果当前行对应的list不存在,就加入一个空list进去。
动态演示如下:

时间复杂度:O(N) 空间复杂度:O(h),h是树的高度
java代码:

import java.util.*;	
class Solution {
	public List<List<Integer>> levelOrder(TreeNode root) {
		if(root==null) {
			return new ArrayList<List<Integer>>();
		}
		//用来存放最终结果
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		dfs(1,root,res);
		return res;
	}
	
	void dfs(int index,TreeNode root, List<List<Integer>> res) {
		//假设res是[ [1],[2,3] ], index是3,就再插入一个空list放到res中
		if(res.size()<index) {
			res.add(new ArrayList<Integer>());
		}
		//将当前节点的值加入到res中,index代表当前层,假设index是3,节点值是99
		//res是[ [1],[2,3] [4] ],加入后res就变为 [ [1],[2,3] [4,99] ]
		res.get(index-1).add(root.val);
		//递归的处理左子树,右子树,同时将层数index+1
		if(root.left!=null) {
			dfs(index+1, root.left, res);
		}
		if(root.right!=null) {
			dfs(index+1, root.right, res);
		}
	}
}                                                                                       

python代码:

class Solution(object):
	def levelOrder(self, root):
		"""
		:type root: TreeNode
		:rtype: List[List[int]]
		"""
		if not root:
			return []
		res = []
		def dfs(index,r):
			# 假设res是[ [1],[2,3] ], index是3,就再插入一个空list放到res中
			if len(res)<index:
				res.append([])
			#  将当前节点的值加入到res中,index代表当前层,假设index是3,节点值是99
			# res是[ [1],[2,3] [4] ],加入后res就变为 [ [1],[2,3] [4,99] ]
			res[index-1].append(r.val)
			# 递归的处理左子树,右子树,同时将层数index+1
			if r.left:
				dfs(index+1,r.left)
			if r.right:
				dfs(index+1,r.right)
		dfs(1,root)
		return res
                                                                                                                   

(全文完)

6 次阅读

发表评论

电子邮件地址不会被公开。