力扣hot100刷题笔记——二叉树类型
admin
2024-05-15 04:21:17
0

二叉树类型题目

94. 二叉树的中序遍历
  题目概述:给定一个二叉树的根节点 root ,返回 它的中序遍历 。

/*** 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 {public List inorderTraversal(TreeNode root) {/* 1.第一种方案,递归*/List res = new ArrayList<>();inorderTraversalHelper(root, res);return res;}public void inorderTraversalHelper(TreeNode root, List res) {if (root == null) {return;} else {inorderTraversalHelper(root.left, res);res.add(root.val);inorderTraversalHelper(root.right, res);return;}}
}

98. 验证二叉搜索树
  题目概述:给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下:节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

/*** 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 {public boolean isValidBST(TreeNode root) {/* 1.第一种方案递归思路错误,没有考虑到子树节点值和更上层根节点冲突的情况*/if (root == null) {return true;} else if (root.left == null && root.right == null) {return true;} else if (root.left == null) {return root.right.val > root.val && isValidBST(root.right);} else if (root.right == null) {return root.left.val < root.val && isValidBST(root.left);} else {return root.left.val < root.val && root.right.val > root.val && isValidBST(root.left) && isValidBST(root.right); }/* 2.第二种方案,参考的题解递归,将约束条件使用辅助函数传入*/return isValidBSTHelper(root, null, null);/* 3.第三种方案,参考的题解中序遍历的结果为升序*/List res = new ArrayList<>();getNodeValue(root, res);return check(res);}public void getNodeValue(TreeNode root, List res) {if (root == null) {return;} else {getNodeValue(root.left, res);res.add(root.val);getNodeValue(root.right, res);return;}}public boolean check(List res) {for (int i = 1; i < res.size(); i++) {if (res.get(i) <= res.get(i - 1)) {return false;}}return true;}public boolean isValidBSTHelper(TreeNode root, TreeNode min, TreeNode max) {if (root == null) {return true;}if (min != null && root.val <= min.val) {return false;}if (max != null && root.val >= max.val) {return false;}return isValidBSTHelper(root.left, min, root) && isValidBSTHelper(root.right, root, max);}
}

297. 二叉树的序列化与反序列化
  题目概述:序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Codec {// Encodes a tree to a single string./* 1.第一种方案,参考的题解递归,先序遍历使用x区分空节点*/public String serialize(TreeNode root) {if (root == null) {return "x,";} else {StringBuilder curNode = new StringBuilder();curNode.append(String.valueOf(root.val));curNode.append(",");curNode.append(serialize(root.left));curNode.append(serialize(root.right));return curNode.toString();}}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {String[] str_word = data.split(",");List list_word = new LinkedList(Arrays.asList(str_word));return deserializeHelper(list_word);}public TreeNode deserializeHelper(List list_word) {if (list_word.size() == 0) {return null;} else if (list_word.get(0).equals("x")) {list_word.remove(0);return null;} else {TreeNode root = new TreeNode();root.val = Integer.valueOf(list_word.get(0));list_word.remove(0);root.left = deserializeHelper(list_word);root.right = deserializeHelper(list_word);return root;}}
}// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

538. 把二叉搜索树转换为累加树
  题目概述:给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。提醒一下,二叉搜索树满足下列约束条件:节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。

/*** 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 {private int sum = 0;public TreeNode convertBST(TreeNode root) {/* 1.第一种方案递归,中序遍历将所有节点的值以升序存入数组将旧、新值存入map中更新tree*/List res = new ArrayList<>();HashMap map = new HashMap<>();getList(root, res);updateList(res, map);updateTree(root, map);return root;/* 2.第二种方案,参考的题解反向中序遍历*/convertBSTHelper(root);return root;}public void convertBSTHelper(TreeNode root) {if (root == null) {return;} else {convertBSTHelper(root.right);int oldValue = root.val;root.val += this.sum;this.sum += oldValue;convertBSTHelper(root.left);}}public void updateTree(TreeNode root, HashMap map) {if (root == null) {return;} else {root.val = map.get(root.val);updateTree(root.left, map);updateTree(root.right, map);}}public void getList(TreeNode root, List res) {if (root == null) {return;} else {getList(root.left, res);res.add(root.val);getList(root.right, res);}}public void updateList(List res, HashMap map) {for (int i = 0; i < res.size(); i++) {int oldValue = res.get(i);res.set(i, oldValue + getSum(res, i));map.put(oldValue, res.get(i));}}public int getSum(List list, int startIdx) {int res = 0;for (int i = startIdx + 1; i < list.size(); i++) {res += list.get(i);}return res;}
}

617. 合并二叉树
  题目概述:给你两棵二叉树: root1 和 root2 。

想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。返回合并后的二叉树。注意: 合并过程必须从两个树的根节点开始。

/*** 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 {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null) {return root2;} else if (root2 == null) {return root1;} else {TreeNode root = new TreeNode(root1.val + root2.val);root.left = mergeTrees(root1.left, root2.left);root.right = mergeTrees(root1.right, root2.right);return root;}}
}

二叉树类型总结

  总结,二叉树类型天然适合使用递归来求解,和链表一样,是练习递归很好的样例。



To be a sailor of the world bound for all ports.

相关内容

热门资讯

linux入门---制作进度条 了解缓冲区 我们首先来看看下面的操作: 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统(六):学... 8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤: 在Student.cpp的...
JAVA多线程知识整理 Java多线程基础 线程的创建和启动 继承Thread类来创建并启动 自定义Thread类的子类&#...
【洛谷 P1090】[NOIP... [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G ...
国民技术LPUART介绍 低功耗通用异步接收器(LPUART) 简介 低功耗通用异步收发器...
城乡供水一体化平台-助力乡村振... 城乡供水一体化管理系统建设方案 城乡供水一体化管理系统是运用云计算、大数据等信息化手段࿰...
程序的循环结构和random库...   第三个参数就是步长     引入文件时记得指明字符格式,否则读入不了 ...
中国版ChatGPT在哪些方面... 目录 一、中国巨大的市场需求 二、中国企业加速创新 三、中国的人工智能发展 四、企业愿景的推进 五、...
报名开启 | 共赴一场 Flu... 2023 年 1 月 25 日,Flutter Forward 大会在肯尼亚首都内罗毕...
汇编00-MASM 和 Vis... Qt源码解析 索引 汇编逆向--- MASM 和 Visual Studio入门 前提知识ÿ...
【简陋Web应用3】实现人脸比... 文章目录🍉 前情提要🌷 效果演示🥝 实现过程1. u...
前缀和与对数器与二分法 1. 前缀和 假设有一个数组,我们想大量频繁的去访问L到R这个区间的和,...
windows安装JDK步骤 一、 下载JDK安装包 下载地址:https://www.oracle.com/jav...
分治法实现合并排序(归并排序)... 🎊【数据结构与算法】专题正在持续更新中,各种数据结构的创建原理与运用✨...
在linux上安装配置node... 目录前言1,关于nodejs2,配置环境变量3,总结 前言...
Linux学习之端口、网络协议... 端口:设备与外界通讯交流的出口 网络协议:   网络协议是指计算机通信网...
Linux内核进程管理并发同步... 并发同步并发 是指在某一时间段内能够处理多个任务的能力,而 并行 是指同一时间能够处理...
opencv学习-HOG LO... 目录1. HOG(Histogram of Oriented Gradients,方向梯度直方图)1...
EEG微状态的功能意义 导读大脑的瞬时全局功能状态反映在其电场结构上。聚类分析方法一致地提取了四种头表面脑电场结构ÿ...
【Unity 手写PBR】Bu... 写在前面 前期积累: GAMES101作业7提高-实现微表面模型你需要了解的知识 【技...