力扣-Hot100-二叉树其一【算法学习day.32】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.二叉树的直径

题目链接:543. 二叉树的直径 - 力扣（LeetCode）

题面:

基本分析:用recursion（i）表示i节点的最长子链长

代码:

/**
 * 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 ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
      recursion(root);
      return ans;
    }
    public int recursion(TreeNode root){
      if(root==null)return -1;
      int left = recursion(root.left)+1;
      int right = recursion(root.right)+1;
      ans = Math.max(ans,left+right);
      return Math.max(left,right);
    }
    
}

2.二叉树的层序遍历

题目链接:102. 二叉树的层序遍历 - 力扣（LeetCode）

题面:

基本分析:使用队列实现bfs

代码:

/**
 * 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 {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        Queue<TreeNode> queue2 = new ArrayDeque<>();
        if(root==null)return ans;
        int flag = 0;
        queue.offer(root);
        while(true){
        List<Integer> list = new ArrayList<>();
          if(flag%2==0){
          if(queue.isEmpty())break;
          while(!queue.isEmpty()){
          TreeNode node =  queue.poll();
          list.add(node.val);
          if(node.left!=null)queue2.offer(node.left);
          if(node.right!=null)queue2.offer(node.right);
         }
         }

         else{
          if(queue2.isEmpty())break;
          while(!queue2.isEmpty()){
          TreeNode node = queue2.poll();
          list.add(node.val);
           if(node.left!=null)queue.offer(node.left);
          if(node.right!=null)queue.offer(node.right);
        }
         }
         ans.add(list);
         flag++;
        }
        return ans;
    }
}

3.二叉搜索树中第K小的元素

题目链接:230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

题面:

基本分析:中序遍历

代码:

/**
 * 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[] arr = new int[10005];
    int count = 0;
    public int kthSmallest(TreeNode root, int k) {
        recursion(root);
        return arr[k-1];
    }
    public void recursion(TreeNode root){
       if(root==null)return;
       recursion(root.left);
       arr[count++] = root.val;
       recursion(root.right);
    }
}

4.二叉树的右视图

题目链接:199. 二叉树的右视图 - 力扣（LeetCode）

题面:

基本分析:使用bfs存队列，每次结束后的队列头就是该层的最右边元素

代码:

/**
 * 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 {
     List<Integer> ans = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        if(root==null)return ans;
     Queue<TreeNode> queue = new ArrayDeque<>();
     Queue<TreeNode> queue2 = new ArrayDeque<>();
     queue.offer(root);
     int flag = 0;
     while(true){
        if(flag%2==0){
            if(queue.isEmpty())break;
          TreeNode right= queue.peek();
            ans.add(right.val);
            while(!queue.isEmpty()){
               TreeNode node =  queue.poll();
               if(node.right!=null)queue2.offer(node.right);
               if(node.left!=null)queue2.offer(node.left);
            }
        }else{
            if(queue2.isEmpty())break;
            TreeNode right= queue2.peek();
            ans.add(right.val);
            while(!queue2.isEmpty()){
               TreeNode node =  queue2.poll();
               if(node.right!=null)queue.offer(node.right);
               if(node.left!=null)queue.offer(node.left);
            }

        }
        flag++;
     }
     return ans;
    }
}

5.二叉树展开为链表

题目链接:114. 二叉树展开为链表 - 力扣（LeetCode）

题面:

吐槽：这题被Java的引用闹麻了，贴上大佬代码

代码:

class Solution {
    public void flatten(TreeNode root) {
        if(root == null){
            return ;
        }
        //将根节点的左子树变成链表
        flatten(root.left);
        //将根节点的右子树变成链表
        flatten(root.right);
        TreeNode temp = root.right;
        //把树的右边换成左边的链表
        root.right = root.left;
        //记得要将左边置空
        root.left = null;
        //找到树的最右边的节点
        while(root.right != null) root = root.right;
        //把右边的链表接到刚才树的最右边的节点
        root.right = temp;
    }
}