【基础算法精讲 13】二叉树的层序遍历 102. 二叉树的层序遍历给你二叉树的根节点root返回其节点值的层序遍历。 即逐层地从左到右访问所有节点。思路1使用双数组1.记录当前节点的数组2.记录下一次要遍历节点的数组3.用下次遍历的数组替代当前节点的数组 代码 做法1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{publicListListIntegerlevelOrder(TreeNoderoot){ListTreeNodecurnewArrayList();ListListIntegeransnewArrayList();if(rootnull){returnans;}cur.add(root);while(!cur.isEmpty()){ListTreeNodenxtnewArrayList();// 保存当前层数值ListIntegerlevelValnewArrayList(cur.size());for(inti0;icur.size();i){rootcur.get(i);levelVal.add(root.val);if(root.left!null)nxt.add(root.left);if(root.right!null)nxt.add(root.right);}ans.add(levelVal);curnxt;}returnans;}}做法2classSolution{publicListListIntegerlevelOrder(TreeNoderoot){if(rootnull){//List.of() 是 Java 9 新增的静态工厂方法快速创建不可变只读List。//调用 add() / remove() / set() 直接抛 UnsupportedOperationExceptionreturnList.of();}ListTreeNodecurList.of(root);ListListIntegeransnewArrayList();while(!cur.isEmpty()){ListTreeNodenxtnewArrayList();// 保存当前层数值ListIntegerlevelValnewArrayList(cur.size());for(TreeNodenode:cur){levelVal.add(node.val);if(node.left!null)nxt.add(node.left);if(node.right!null)nxt.add(node.right);}ans.add(levelVal);curnxt;}returnans;}}思路2二叉树层序遍历的标准做法是使用层序遍历 代码classSolution{publicListListIntegerlevelOrder(TreeNoderoot){if(rootnull){returnList.of();}QueueTreeNodeqnewLinkedList();ListListIntegeransnewArrayList();q.add(root);while(!q.isEmpty()){ListIntegerlevelValnewArrayList();//当前层节点数量intnq.size();for(inti0;in;i){TreeNodenodeq.poll();levelVal.add(node.val);if(node.left!null)q.add(node.left);if(node.right!null)q.add(node.right);}ans.add(levelVal);}returnans;}}103. 二叉树的锯齿形层序遍历给你二叉树的根节点root返回其节点值的锯齿形层序遍历。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。思路奇数层是从左到右遍历偶数层从右到左遍历用一个bool值判断奇偶层。 代码classSolution{publicListListIntegerzigzagLevelOrder(TreeNoderoot){if(rootnull){returnList.of();}QueueTreeNodeqnewLinkedList();ListListIntegeransnewArrayList();q.add(root);//用于判断奇偶层booleanflagtrue;while(!q.isEmpty()){ListIntegerlevelValnewArrayList();//当前层节点数量intnq.size();for(inti0;in;i){TreeNodenodeq.poll();levelVal.add(node.val);if(node.left!null)q.add(node.left);if(node.right!null)q.add(node.right);}if(!flag){Collections.reverse(levelVal);}ans.add(levelVal);flag!flag;}returnans;}}513. 找树左下角的值给定一个二叉树的根节点root请找出该二叉树的最底层 最左边节点的值。假设二叉树中至少有一个节点。思路1:从右到左遍历最后一个节点就是最底层左边节点的值。 代码classSolution{publicintfindBottomLeftValue(TreeNoderoot){QueueTreeNodeqnewLinkedList();q.add(root);while(!q.isEmpty()){rootq.poll();if(root.right!null)q.add(root.right);if(root.left!null)q.add(root.left);}returnroot.val;}}思路2之前【基础算法精讲10】如何灵活运用递归里面有一道题二叉树右视图。可以在此基础上继续修改变为二叉树的左视图。最后一个节点就是最底层最左边节点的值。 代码classSolution{ListIntegeransnewArrayList();publicvoiddepth(TreeNodenode,intdepth){if(nodenull)return;depth1;if(depthans.size()){ans.add(node.val);}//遍历左子树depth(node.left,depth);//遍历右子树depth(node.right,depth);}publicintfindBottomLeftValue(TreeNoderoot){depth(root,0);returnans.get(ans.size()-1);}}