二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7 返回其层序遍历结果： [ [3], [9,20], [15,7] ]
分析
二叉树层序遍历过程详细看这篇，直接套魔板即可。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>>list=new ArrayList<List<Integer>>(); if(root==null)return list; Queue<TreeNode>q1=new ArrayDeque<TreeNode>(); q1.add(root); while (!q1.isEmpty()) { int size=q1.size(); List<Integer>value=new ArrayList<Integer>(); for(int i=0;i<size;i++) { TreeNode pNode=q1.poll(); if(pNode.left!=null) q1.add(pNode.left); if(pNode.right!=null) q1.add(pNode.right); value.add(pNode.val); } list.add(value); } return list; } }
二叉树锯齿形遍历
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回锯齿形层序遍历如下： [ [3], [20,9], [15,7] ]
分析：
就是一个特殊的层序遍历。更换层的时候需要更换节点顺序，这需要我们用两个内存空间配合达到分清奇偶的目的。这里有的是从左到右，有的是从右到左，理论上可以借助栈将集合的元素反转但是没必要。我用两个List集合直接刚就行了。
首先进行分析：
- 第一行从左到右，第二行从右到左，第三行从左到右。两个list装的是节点，而还需要每次遍历根据奇数和偶数的特性将节点装起来。
- (普遍方法)你可以全部按照正常的顺序分层装起来，只不过如果偶数层遍历的时候从右往左加进结果集合。比较好想，容易操作，但是偶数层在添加节点时候不能同时遍历。
- 但是笔者瞎搞发现一个规律。全部从右往左遍历。只不过在奇数行先添加(左后右)。而偶数行进行右左添加，相当于这个顺序操作一次被颠倒一次，每次添加节点都可以直接访问而不需要单独的访问。(这个方法可能复杂了上面一条其实就可以了)
实现代码为：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>>list=new ArrayList<List<Integer>>(); if(root==null)return list; ArrayList<TreeNode>nodelist1=new ArrayList<TreeNode>();//用来模拟堆栈用 ArrayList<TreeNode>nodelist2=new ArrayList<TreeNode>(); nodelist1.add(root); int num=1;//做奇数偶数 while (!nodelist1.isEmpty()||!nodelist2.isEmpty()) { ArrayList<Integer>team=new ArrayList<Integer>(); if(num%2==1) { for(int i=nodelist1.size()-1;i>=0;i--) { TreeNode teamNode=nodelist1.get(i); team.add(teamNode.val); if(teamNode.left!=null)nodelist2.add(teamNode.left); if(teamNode.right!=null)nodelist2.add(teamNode.right); } nodelist1.clear(); } else { for(int i=nodelist2.size()-1;i>=0;i--) { TreeNode teamNode=nodelist2.get(i); team.add(teamNode.val); if(teamNode.right!=null)nodelist1.add(teamNode.right); if(teamNode.left!=null)nodelist1.add(teamNode.left); } nodelist2.clear(); } list.add(team); num++; } return list; } }
二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。
分析
可以使用二叉树的遍历同时记录深度，保存最大的深度即可。
具体代码为：
/** * 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; * } * } */ class Solution { int maxhigh; public int maxDepth(TreeNode root) { maxDepth(root,0); return maxhigh; } private void maxDepth(TreeNode root, int high) { // TODO Auto-generated method stub if(high>maxhigh) maxhigh=high; if(root==null) return ; else { maxDepth(root.left, high+1); maxDepth(root.right, high+1); } } }
原创不易，bigsai请你帮两件事帮忙一下:
star支持一下， 您的肯定是我在平台创作的源源动力。
微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见！
