LeetCode 102二叉树的层序遍历&103二叉树锯齿形遍历&104二叉树的最大深度

你的名字 2023-01-04 14:40 122阅读 0赞

> **微信搜一搜**：`bigsai`  
> **[大家都在关注的刷题、学习数据结构和算法宝藏项目][Link 1]**  
> 关注回复**进群**即可加入力扣打卡群，欢迎划水。近期打卡：  
> [LeetCode 97交错字符串(动态规划)][LeetCode 97]  
> [LeetCode 98验证二叉搜素树(中序遍历)&99恢复二叉搜索树][LeetCode 98_99]  
> [LeetCode 100相同的树&101对称二叉树][LeetCode 100_101]

## 二叉树的层序遍历 ##

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：  
二叉树：\[3,9,20,null,null,15,7\],

3
       / \
      9  20
        /  \
       15   7
    返回其层序遍历结果：
    
    [
      [3],
      [9,20],
      [15,7]
    ]

**分析**  
二叉树层序遍历过程详细看[这篇][Link 2]，直接套魔板即可。

## 二叉树锯齿形遍历 ##

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

给定二叉树 [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请你帮两件事帮忙一下:

1.  star支持一下， 您的肯定是我在平台创作的源源动力。
2.  微信搜索「**bigsai**」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

![image-20201114211553660][]

[Link 1]: https://github.com/javasmall/bigsai-algorithm
[LeetCode 97]: https://bigsai.blog.csdn.net/article/details/112134215
[LeetCode 98_99]: https://bigsai.blog.csdn.net/article/details/112135002
[LeetCode 100_101]: https://bigsai.blog.csdn.net/article/details/112439370
[Link 2]: https://bigsai.blog.csdn.net/article/details/99745321
[image-20201114211553660]: /images/20221119/5661bffaaf1f4c6d929d9d96f1844304.png