当前位置: 首页 > 科技观察

说说从上到下打印一棵二叉树

时间:2023-03-20 20:11:59 科技观察

Leetcode:一:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof二:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof三:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof"GitHub:https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_25_levelOrder/Solution.javaPrintbinarytreeIfromtoptobottom》题目描述:从上到下打印二叉树的每个节点,从左到右打印同级的节点。例如:给定一棵二叉树:[3,9,20,null,null,15,7],3/\920/\157返回:[3,9,20,15,7]提示:节点总数<=1000解题思路:题目要求的二叉树自上而下打印(即逐层打印),也称为二叉树的广度优先搜索(BFS)。BFS通常是借助于队列的先进先出特性来实现的。算法流程:特例处理:当树的根节点为空时,直接返回空列表[];初始化:打印结果列表res=[],包含根节点的队列queue=[root];BFS循环:当queue队列为空时跳出;出队:队列的第一个元素出队,记录为节点;打印:将node.val添加到列表tmp的末尾;添加子节点:如果node的左(右)子节点不为空,则添加Right)子节点加入queue队列;返回值:只返回打印结果列表res。复杂度分析:时间复杂度O(N):N为二叉树的节点数,即BFS需要循环N次。空间复杂度O(N):最坏情况下,当树为平衡二叉树时,至多N/2个树节点同时在队列中,使用O(N)大小的额外空间。packagecom.nateshao.sword_offer.topic_25_levelOrder;导入java.util.ArrayList;导入java。@个人网站www.nateshao.cn*@bloghttps://nateshao.gitee.io*@GitHubhttps://github.com/nateshao*@Giteehttps://gitee.com/nateshao*说明:从上到下打印二叉树思路:使用队列(链表)辅助实现。**add如果队列已满,则添加一个元素,抛出IIIegaISlabEepeplian异常*remove如果队列为空,则移除并返回队列头部的元素,抛出NoSuchElementException*element如果出现,则返回队列头部的元素queue如果为空,抛出NoSuchElementException*offer添加一个元素并返回true如果队列已满,返回false*poll移除并返回队列头部的元素如果队列为空,返回null*peek返回如果队列为空,则返回队列的头部,返回null*put如果队列已满,则添加一个元素,阻塞*如果队列为空,则移除并返回队列头部的元素,阻塞*/publicclassSolution{/***queue**@paramroot*@return*/publicint[]levelOrder(TreeNoderoot){if(root==null)returnnewint[0];//空树返回空数组ArrayListlist=newArrayList<>();//申请一个动态数组ArrayList动态添加节点值Queuequeue=newLinkedList<>();queue.offer(root);//根节点先入队while(!queue.isEmpty()){TreeNodenode=queue.poll();//取出当前队列的第一个元素list.add(node.val);if(node.left!=null)queue.offer(node.left);//左子节点加入队列if(node.right!=null)queue.offer(node.right);//右子节点入队}//将ArrayList转为int数组返回int[]res=newint[list.size()];for(inti=0;iPrintFromTopToBottom2(TreeNoderoot){ArrayListlist=newArrayList();if(root==null){returnlist;}list.add(root.val);levelOrder(root,list);returnlist;}publicvoidlevelOrder(TreeNoderoot,ArrayListlist){if(root==null){return;}if(root.left!=null){list.add(root.left.val);}if(root.right!=null){list.add(root.right.val);}levelOrder(root.left,list);levelOrder(root.right,list);}publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx){val=x;}}}从上到下打印一棵二叉树II题目描述:从上到下逐层打印一棵二叉树,同一层的节点从左到右依次打印,每一层打印一行"例如:给定一棵二叉树:[3,9,20,null,null,15,7],3/\920/\157返回其层次遍历结果:[[3],[9,20],[15,7]]publicList>levelOrder(TreeNoderoot){Queuequeue=newLinkedList<>();List>res=newArrayList<>();if(root!=null)queue.add(root);while(!queue.isEmpty()){Listtmp=newArrayList<>();for(inti=queue.size();i>0;i--){TreeNodenode=queue.poll();tmp.add(node.val);if(node.left!=null)queue.add(node.left);if(node.right!=null)queue.add(node.right);}res.add(tmp);}returnres;}III.从上到下打印一棵二叉树III》题目描述:请实现一个函数,按照Z字形顺序打印一棵二叉树,即打印第一行按从左到右的顺序,第一行从左到右打印。第二层从右到左打印,第三行从左到右打印,其他行以此类推。例如:给定一棵二叉树:[3,9,20,null,null,15,7],3/\920/\157返回其层次遍历结果:[[3],[20,9],[15,7]]classSolution{publicList>levelOrder(TreeNoderoot){Dequedeque=newLinkedList<>();List>res=newArrayList<>();if(root!=null)deque.add(root);while(!deque.isEmpty()){//打印奇数层Listtmp=newArrayList<>();for(inti=deque.size();i>0;i--){//从左到右打印TreeNodenode=deque.removeFirst();tmp.add(node.val);//从左到右添加下层节点if(node.left!=null)deque.addLast(node.left);if(node.right!=null)deque.addLast(node.right);}res.add(tmp);if(deque.isEmpty())break;//如果为空,早早跳出//打印偶数层tmp=newArrayList<>();for(inti=deque.size();i>0;i--){//从右到左打印TreeNodenode=deque.removeLast();tmp.add(node.val);//先右后左添加下节点if(node.right!=null)deque.addFirst(node.right);if(node.left!=null)deque.addFirst(node.left);}res.add(tmp);}returnres;}}参考链接:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/solution/mian-shi-ti-32-i-cong-shang-dao-xia-da-yin-er-ch-4https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solution/mian-shi-ti-32-ii-cong-shang-dao-xia-da-yin-er-c-5https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/mian-shi-ti-32-iii-cong-shang-dao-xia-da-yin-er--3