day14

1、层序遍历

1. 102.二叉树的层序遍历

   class Solution {
       public List<List<Integer>> levelOrder(TreeNode root) {
           List<List<Integer>> resList = new ArrayList<List<Integer>>();
           Queue<TreeNode> que = new LinkedList<TreeNode>();
   
           if(root != null){
               que.add(root);
           }
   
           while(!que.isEmpty()){
               int size = que.size();
               List<Integer> list = new ArrayList<Integer>();
   
               for(int i=0; i<size; i++){
                   TreeNode node = que.poll();
                   list.add(node.val);
                   if(node.left != null){
                       que.offer(node.left);
                   }
                   if(node.right != null){
                       que.offer(node.right);
                   }
               }
               resList.add(list);
           }
   
           return resList;
   
       }
   }
   

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

   class Solution {
       public List<List<Integer>> levelOrderBottom(TreeNode root) {
           List<List<Integer>> resList = new ArrayList<List<Integer>>();
           Queue<TreeNode> que = new LinkedList<TreeNode>();
   
           if(root != null){
               que.add(root);
           }
   
           while(!que.isEmpty()){
               int size = que.size();
               List<Integer> list = new ArrayList<Integer>();
   
               for(int i=0; i<size; i++){
                   TreeNode node = que.poll();
                   list.add(node.val);
                   if(node.left != null){
                       que.offer(node.left);
                   }
                   if(node.right != null){
                       que.offer(node.right);
                   }
               }
               resList.add(list);
           }
   		
   		//将上一题的结果翻转一下就行了
           List<List<Integer>> result = new ArrayList<>();
           for (int i = resList.size() - 1; i >= 0; i-- ) {
               result.add(resList.get(i));
           }
   
           return result;
   
       }
   }
   

3. 199.二叉树的右视图

   class Solution {
       public List<Integer> rightSideView(TreeNode root) {
           List<Integer> res = new ArrayList<Integer>();
           Queue<TreeNode> que = new LinkedList<TreeNode>();
   
           if(root != null){
               que.offer(root);
           }  
   
           while(!que.isEmpty()){
               int size = que.size();
               for (int i = 0; i < size; i++) {
                   TreeNode node = que.poll();
                   if(i==size-1){// 将每一层的最后元素放入result数组中
                       res.add(node.val);
                   }
                   if(node.left != null){
                       que.offer(node.left);
                   }
                   if(node.right != null){
                       que.offer(node.right);
                   }
               }
           }
   
           return res;
   
       }
   }
   

4. 637.二叉树的层平均值

   class Solution {
       public List<Double> averageOfLevels(TreeNode root) {
           Queue<TreeNode> que = new LinkedList<TreeNode>();
           List<Double> list = new ArrayList<Double>();
   
           if(root != null){
               que.offer(root);
           }  
   
           while(!que.isEmpty()){
               int size = que.size();
               double sum = 0.0;
   
               for(int i=0; i<size; i++){
                   TreeNode node = que.poll();
                   sum += node.val;
                   if(node.left != null){
                       que.offer(node.left);
                   }
                   if(node.right != null){
                       que.offer(node.right);
                   }
               }
               list.add(sum/size);
           }
           return list;
       }
   }
   

5. 429.N叉树的层序遍历

   class Solution {
       public List<List<Integer>> levelOrder(Node root) {
           List<List<Integer>> resList = new ArrayList<List<Integer>>();
           Queue<Node> que = new LinkedList<Node>();
   
           if(root != null){
               que.offer(root);
           }
   
           while(!que.isEmpty()){
               int size = que.size();
               List<Integer> list = new ArrayList<Integer>();
   
               for(int i=0; i<size; i++){
                   Node node = que.poll();
                   list.add(node.val);
                   for(int j=0; j<node.children.size(); j++){// 将节点孩子加入队列
                       if(node.children.get(j) != null){
                           que.offer(node.children.get(j));
                       }
                   }
               }
               resList.add(list);
           }
   
           return resList;
           
       }
   }
   

6. 515.在每个树行中找最大值

   class Solution {
       public List<Integer> largestValues(TreeNode root) {
           Queue<TreeNode> que = new LinkedList<TreeNode>();
           List<Integer> list = new ArrayList<Integer>();
   
           if(root != null){
               que.offer(root);
           }  
   
           while(!que.isEmpty()){
               int size = que.size();
               int max = Integer.MIN_VALUE;
   
               for(int i=0; i<size; i++){
                   TreeNode node = que.poll();
                   max = Math.max(node.val,max);
                   if(node.left != null){
                       que.offer(node.left);
                   }
                   if(node.right != null){
                       que.offer(node.right);
                   }
               }
               list.add(max);
           }
           return list;
   
       }
   }
   

7. 116.填充每个节点的下一个右侧节点指针

8. 117.填充每个节点的下一个右侧节点指针II

9. 104.二叉树的最大深度

   class Solution {
       public int maxDepth(TreeNode root) {
           Queue<TreeNode> que = new LinkedList<TreeNode>();
           int depth = 0;
   
           if(root != null){
               que.offer(root);
           }
   
           while(!que.isEmpty()){
               int size = que.size();
               depth++;
   
               for(int i=0; i<size; i++){
                   TreeNode node = que.poll();
                   if(node.left != null){
                       que.offer(node.left);
                   }
                   if(node.right != null){
                       que.offer(node.right);
                   }
               }
           }
           return depth;
       }
   }
   

10. 111.二叉树的最小深度

    class Solution {
        public int minDepth(TreeNode root) {
            Queue<TreeNode> que = new LinkedList<TreeNode>();
            int depth = 0;
    
            if(root != null){
                que.offer(root);
            }
    
            while(!que.isEmpty()){
                int size = que.size();
                depth++;
    
                for(int i=0; i<size; i++){
                    TreeNode node = que.poll();
                    if(node.right==null && node.left==null){
                        return depth;
                    }
                    if(node.left != null){
                        que.offer(node.left);
                    }
                    if(node.right != null){
                        que.offer(node.right);
                    }
                }
            }
            return depth;
        }
    }
    

2、leetcode226 翻转二叉树（优先掌握递归）

1. 思路

   

   只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

   使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！

   那么层序遍历可以不可以呢？依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！

2. 代码实现

   class Solution {
       public TreeNode invertTree(TreeNode root) {
           if(root==null){
               return null;
           }
   
           swapChildren(root); // 中
           invertTree(root.left); //左
           invertTree(root.right); //右
           return root;
       }
   
       private void swapChildren(TreeNode root) {
           TreeNode tmp = root.left;
           root.left = root.right;
           root.right = tmp;
       }
   }
   

3、leetcode101 对称二叉树 （优先掌握递归）

1. 若左右子树可以相互翻转，则该二叉树则为对称二叉树，采用后序遍历，因为要将左右孩子节点的情况反馈给上一层父节点。

2. 代码实现

   class Solution {
       public boolean isSymmetric(TreeNode root) {
           return compare(root.left, root.right);
       }
   
       private boolean compare(TreeNode left, TreeNode right) {
           if (left == null && right != null) {
               return false;
           }else if (left != null && right == null) {
               return false;
           }else if (left == null && right == null) {
               return true;
           }else if (left.val != right.val) {
               return false;
           }
           boolean compareOutside = compare(left.left, right.right);
           boolean compareInside = compare(left.right, right.left);
           return compareOutside && compareInside;
       }
   }