力扣-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;
}
}
后言
上面是力扣Hot100的二叉树专题，下一篇是该专题的其他题目，希望有所帮助，一同进步，共勉！
原文地址：https://blog.csdn.net/2301_79232523/article/details/143751214
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！