手撕面试题算法<树> (1) —— 树的层序遍历以及相关题解

   日期:2020-10-13     浏览:86    评论:0    
核心提示:前言刚开始写算法题时,看到树的题就要烦死了,现在比以前好了点,但也总是忘记思路(毕竟日常真的很少用到这些),开一个坑记录一下树相关的题解吧~导航前言树的层序遍历题解剑指 Offer 32 - II. 从上到下打印二叉树 IILeetCode 107. 二叉树的层次遍历 II剑指 Offer 32 - III. 从上到下之字形打印二叉树 III树的层序遍历从最基本的二叉树开始,树的层序遍历通常来说就是按照树的层数,从上往下的将每一层,按每一层从左到右的顺序遍历出来:剑指 Offer 32 - I.

前言

刚开始写算法题时,看到树的题就要烦死了,现在比以前好了点,但也总是忘记思路(毕竟日常真的很少用到这些),开一个坑记录一下树相关的题解吧~

导航

  • 前言
  • 树的层序遍历
  • 题解
    • 剑指 Offer 32 - II. 从上到下打印二叉树 II
    • LeetCode 107. 二叉树的层次遍历 II
    • 剑指 Offer 32 - III. 从上到下之字形打印二叉树 III

树的层序遍历

从最基本的二叉树开始,树的层序遍历通常来说就是按照树的层数,从上往下的将每一层,按每一层从左到右的顺序遍历出来:

剑指 Offer 32 - I. 从上到下打印二叉树

像这样的二叉树,通过层序遍历遍历出来的结果应该是[3,9,20,15,17]

在没有任何其它特殊要求的情况下,我们借助队列直接把树层序遍历出来:

import java.util.*;
class Solution { 
    public int[] levelOrder(TreeNode root) { 
        List<Integer> res=new ArrayList<>();
        // 空值检测 
        if(root == null){ 
            return new int[0];
        }
        // 借助队列在存放树节点
        Queue<TreeNode> queue=new LinkedList<>();
        
        queue.offer(root);
        while(!queue.isEmpty()){ 
        	// 拿出队头进行操作
        	TreeNode tmp = queue.poll();
        	// 这里的入队操作是先左后右,保证每层的打印顺序是从左到右
        	// 当队头的左节点非空,将其左节点入队
            if(tmp.left != null){ 
                queue.offer(tmp.left);
            }
        	// 当队头的左节点非空,将其左节点入队
            if(tmp.right != null){ 
                queue.offer(tmp.right);
            }
            // 将当前取出的队头输出(添加到结果列表)
        	res.add(tmp.val);
        }
        // 将List转化为int[]
    	return res.stream().mapToInt(Integer::valueOf).toArray();
	}
}

题解

学会了用队列来做层序遍历后,我们会遇到一些题目让你应用层序遍历来解题,如:

剑指 Offer 32 - II. 从上到下打印二叉树 II

力扣链接

和之前简单的打印出一个数组相比,这道题还需要对每一层的节点进行分割,加大了难度
我们可以在之前的基础上改造一下,使层次遍历的每一层都能在我们的掌握之中

    public List<List<Integer>> levelOrder(TreeNode root) { 
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){ 
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){ 
        	// 每次进入while循环时,判断【当前队列】长度
            int len = queue.size();
            // 创建一个ArrayList对象
            // 用来添加当前层(即【当前队列】)的节点值
            List<Integer> list = new ArrayList<>();
            // 遍历【当前队列】
            while(len-- > 0){ 
                TreeNode tmp = queue.poll(); 
                if(tmp.left != null){ 
                    queue.offer(tmp.left);
                }
                if(tmp.right != null){ 
                    queue.offer(tmp.right);
                }
                // 将【当前队列】的值都装进list中
                list.add(tmp.val);
            }
            // 将list装入res列表中
            res.add(list);
        }
        return res;
    }

为什么队列的长度=每一层的节点个数呢?我们从第一层开始推:

  • 当队列中只有根节点时,队列长度为1,通过获取根节点的左右节点,并将根节点出队,我们可以得到下一层的队列中有根节点的左节点和右节点
  • 此时队列长度为2,对该队列进行遍历,获取该队列中的节点,并由这些节点获取到这些节点的左/右子节点
  • 在以后的外层while循环中,每一次外层while循环获取到的队列长度都是树每一层的节点个数

LeetCode 107. 二叉树的层次遍历 II

力扣链接

这道题就是将剑指 Offer 32 - II. 从上到下打印二叉树 II的输出反过来而已,直接在它的基础上在最后加上Collection.reverse(List list)即可

    public List<List<Integer>> levelOrderBottom(TreeNode root) { 
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){ 
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){ 
            List<Integer> list = new ArrayList<>();
            int len = queue.size();
            while(len-- > 0){ 
                TreeNode tmp=queue.poll();
                if(tmp.left != null){ 
                    queue.offer(tmp.left);
                }
                if(tmp.right != null){ 
                    queue.offer(tmp.right);
                }
                list.add(tmp.val);
            }
            res.add(list);
        }
        // 遍历完反转一下
        Collections.reverse(res);
        return res;
    }

剑指 Offer 32 - III. 从上到下之字形打印二叉树 III

力扣链接

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。


之字形打印的话,最简单的方式,在剑指 Offer 32 - II. 从上到下打印二叉树 II的基础上,只需要活用Collections.reverse(List list)这个方法即可

    public List<List<Integer>> levelOrder(TreeNode root) {         
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){ 
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        // 定义变量reverse,由于是偶数行需要反转,所以初值为false
        boolean reverse = false;
        
        while(!queue.isEmpty()){ 
            int len = queue.size();
            List<Integer> list = new ArrayList<>();
            while(len-- > 0){ 
                TreeNode tmp = queue.poll();                
                if(tmp.left != null){ 
                    queue.offer(tmp.left);
                }
                if(tmp.right != null){ 
                    queue.offer(tmp.right);
                }
                list.add(tmp.val);
            }
            // 当reverse为true时,将list反转
            if(reverse){ 
                Collections.reverse(list);
            }
            // 将reverse取反
            reverse =! reverse;
            res.add(list);
        }
        return res;
    }

通过定义一个布尔类型的变量reverse作为判断是否执行反转列表的操作,可以很轻松的打印出之字形树

 
打赏
 本文转载自:网络 
所有权利归属于原作者,如文章来源标示错误或侵犯了您的权利请联系微信13520258486
更多>最近资讯中心
更多>最新资讯中心
0相关评论

推荐图文
推荐资讯中心
点击排行
最新信息
新手指南
采购商服务
供应商服务
交易安全
关注我们
手机网站:
新浪微博:
微信关注:

13520258486

周一至周五 9:00-18:00
(其他时间联系在线客服)

24小时在线客服