编程之美-分层遍历二叉树

青旅半醒 2022-08-06 15:06 116阅读 0赞

问题：给定一个二叉树，要求按分层遍历该二叉树，即从上到下按层次访问该二叉树（每一层将单独输出一行），每一层要求访问的顺序为从左到右，并将节点依次编号。那么分层遍历如图的二叉树，正确的输出应该为：

1
    2  3
    4  5  6
    7  8

![Image 1][]

![Center][]

![Image 1][]书中还给出了问题2：打印二叉树中的某层次的节点（从左到右），其中根结点为第0层，成功返回true，失败返回false

**分析与解法**

关于二叉树的问题，由于其本身固有的递归特性，通常可以用递归解决。为了解决给出的问题，我们可以发现。当解决问题2时，问题就迎刃而解了。现先分析问题2

假设要访问二叉树第K层的节点，那么其实可以把它转换为分别访问“已该二叉树根结点的左右子节点为根结点的两颗子树”中层次为k-1的节点。如题目中的二叉树，给定k=2，即要求访问原二叉树中第2层的节点（根结点为第0层），可以把它转换为分别访问以节点2、3为根结点的两颗子树中的k-1=1层的节点。

所以遍历第k层节点的代码如下（把最终结果存放在了list里）：

public boolean printNodeAtLevel(TreeNode root, int level, List<Integer> list) {
        	if (root == null || level < 0) {
        		return false;
        	}
        	if (level == 0 && root != null) {
        		list.add(root.val);
        		return true;
        	}
        	boolean left = printNodeAtLevel(root.left, level-1, list);
        	boolean rigth = printNodeAtLevel(root.right, level-1, list);
        	return left || rigth;
        }

所以分层遍历的问题也就解决了，只需要从第0层，一直调用到二叉树的最后一层，就可以完全遍历了。但是二叉树的最大层数怎么求。也是递归的代码：

public int maxDepth(TreeNode root) {
        	if (root == null) {
        		return 0;
        	}
        	int left = 1+maxDepth(root.left); 
        	int rigth = 1+maxDepth(root.right);
        	return left > rigth ? left : rigth;
        }

好了，问题就解决了。好像发现这样的效率太低了。把求深度和遍历某层次的代码合并，得到如下代码：

public List<List<Integer>> levelOrder2(TreeNode root) {
        	List<List<Integer>> lists = new ArrayList<List<Integer>>();
        	if (root == null)
        		return lists;
        	for (int level = 0; ; level++) {
        		List<Integer> list = new ArrayList<>();
        		if (!printNodeAtLevel(root, level, list))
        			break;
        		lists.add(0, list);
        	}
        	return lists;
        }

但是发现，这种效率实在是太低了，因为每次访问都需要从跟节点访问，直到访问完成。下面的代码采用了游标的方式：cur代表当前访问的节点，last代表当前层次的最后一个节点。代码比较好懂，如下：

public List<List<Integer>> levelOrder3(TreeNode root) {
        	List<List<Integer>> lists = new ArrayList<List<Integer>>();
        	if (root == null)
        		return lists;
        	int cur = 0, last = 1;
        	List<TreeNode> queue = new ArrayList<>();
        	queue.add(root);
        	while (cur < queue.size()) {
        		last = queue.size();
        		List<Integer> list = new ArrayList<>();
        		while (cur < last) {
        			TreeNode node = queue.get(cur);
        			list.add(node.val);
        			if (node.right != null) {
        				queue.add(node.right);
        			}
        			if (node.left != null) {
        				queue.add(node.left);
        			}
        			cur++;
        		}
        		lists.add(list);
        	}
        	return lists;
        }

好，至此关于编程之美上面的关于本题的解法就没了。我接下来在说两种方案，是我在没看本书解答时，自己写的。

方法一，是用了两个队列，一个队列存储k-1层的节点，另一个队列存储k层的节点。代码如下：

public List<List<Integer>> levelOrder1(TreeNode root) {
        	List<List<Integer>> lists = new ArrayList<List<Integer>>();
        	if (root == null)
        		return lists;
        	LinkedList<TreeNode> preQueue = new LinkedList<>();
        	LinkedList<TreeNode> curQueue = new LinkedList<>();
        	preQueue.offer(root);
        	curQueue.offer(root);
        	while (!curQueue.isEmpty()) {
        		List<Integer> list = new ArrayList<>();
        		while (!curQueue.isEmpty()) {
        			TreeNode node = curQueue.poll();
            		list.add(node.val);
            	}
        		lists.add(list);
        		while (!preQueue.isEmpty()) {
        			TreeNode node = preQueue.poll();
        			if (node.left != null) {
        				curQueue.offer(node.left);
        			}
        			if (node.right != null) {
        				curQueue.offer(node.right);
        			}
        		}
        		preQueue = new LinkedList<>(curQueue);
        	}
        	return lists;
        }

个人感觉也挺高效的，但是两个队列，实现有点浪费。于是，改造成了如下代码

public List<List<Integer>> levelOrder4(TreeNode root) {
        	List<List<Integer>> lists = new ArrayList<List<Integer>>();
        	if (root == null)
        		return lists;
        	Queue<TreeNode> queue = new LinkedList<>();
        	queue.offer(root);
        	while (!queue.isEmpty()) {
        		int levelNum = queue.size();
        		List<Integer> list = new LinkedList<>();
        		for (int i = 0; i < levelNum; i++) {
        			TreeNode node = queue.poll();
        			if (node.left != null) {
        				queue.offer(node.left);
        			}
        			if (node.right != null) {
        				queue.offer(node.right);
        			}
        			list.add(node.val);
        		}
        		lists.add(0, list);
        	}
        	return lists;
        }

个人感觉，这是四种里面最好的办法了。。。。。你认为呢？

[Image 1]: 
[Center]: /images/20220805/47104397bc24495e84fabf56d3802e28.png