有关二叉树的一些题解
没有将全部思想写上，因为本着本人的一些自私所以都挑选了本人比较熟悉的思想 类名命名为中文纯属个人故意的，业务中千万不要用中文，我只是懒得起名字了
翻转二叉树
迭代
代码语言：javascript复制/**
* @author ZVerify
* @since 2022/10/30 16:41
* @see <a href="https://leetcode.cn/problems/invert-binary-tree/description/">...</a>
**/
public class 翻转二叉树 {
public TreeNode invertTree(TreeNode root) {
if (root==null) return null; // 如果为null直接返回
Deque<TreeNode> linkedList = new LinkedList<>();
linkedList.add(root);
// 广度优先，如果队列里边还有节点说明没转换完
while (!linkedList.isEmpty()){
for (int i = 0; i < linkedList.size(); i ) {
TreeNode first = linkedList.pollFirst();
// 先将子树进行转换然后添加完成其整颗树的翻转
swap(first);
if (first.left!=null) linkedList.offer(first.left);
if (first.right!=null) linkedList.offer(first.right);
}
}
return root;
}
private void swap(TreeNode root) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}对称二叉树
dfs
代码语言：javascript复制public boolean isSymmetric(TreeNode root) {
if (root == null ) return true;
return dfs(root.left, root.right);
}
private boolean dfs(TreeNode left, TreeNode right) {
// 如果当前节点为叶子节点则为对称二叉树，因为当前树只有一个节点;
if (left==null && right==null) return true;
// 如果左节点为null或者右节点为null，又或者两者的val不相同则为false;
if (left==null || right==null || left.val!=right.val) return false;
// 最后考虑完自己本身之后判断左右两颗树，如果都为对称则为对称；
return dfs(left.right,right.left) && dfs(left.left, right.right);
}二叉树的最大深度
迭代
代码语言：javascript复制/**
* @author ZVerify
* @since 2022/10/30 11:43
* @see <a href="https://leetcode.cn/problems/maximum-depth-of-binary-tree/">二叉树的最大深度</a>
**/
public class 二叉树的最大深度 {
public int maxDepth(TreeNode root) {
if (root==null) return 0;
if (root.left == null && root.right == null) return 1;
Deque<TreeNode> list = new LinkedList<>();
list.addLast(root);
int sum = 0;
while (!list.isEmpty()){
int size = list.size();
sum ;
for (int i = 0 ; i<size; i ) {
TreeNode treeNode = list.pollFirst();
if (treeNode.left!=null) list.addLast(treeNode.left);
if (treeNode.right!=null) list.addLast(treeNode.right);
}
}
return sum;
}
}二叉树的最小深度
迭代
代码语言：javascript复制public int minDepth(TreeNode root) {
// 如果为null则返回0
if (root==null) return 0;
// 只有根节点则返回0
if (root.left==null&&root.right==null) return 1;
int sum = 0;
Deque<TreeNode> list = new LinkedList<>();
list.add(root);
// 层序遍历,在过程中碰到哪层含有左右子节点都为null的节点则为最小深度
while (!list.isEmpty()){
sum ;
int size = list.size();
for (int i = 0; i < size; i ) {
TreeNode treeNode = list.pollFirst();
if (treeNode.left!=null) list.add(treeNode.left);
if (treeNode.right!=null) list.add(treeNode.right);
if (treeNode.left==null&&treeNode.right==null) return sum;
}
}
return sum;
}二叉树的所有路径
迭代
代码语言：javascript复制/**
* @author ZVerify
* @since 2022/10/31 08:37
* @see <a href="https://leetcode.cn/problems/binary-tree-paths/comments/">...</a>
**/
public class 二叉树的所有路径 {
List<String> list = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
if (root==null) return list;
// 保存节点
Deque<TreeNode> nodeArrayList = new LinkedList<>();
// 同步节点所经过的路径
Deque<String> strings = new LinkedList<>();
nodeArrayList.addLast(root);
strings.addLast(String.valueOf(root.val));
while (!nodeArrayList.isEmpty()) {
for (int i = 0; i < nodeArrayList.size(); i ) {
TreeNode treeNode = nodeArrayList.pollLast();
String s = strings.pollLast();
if (treeNode.left==null && treeNode.right==null){
list.add(s);
}else {
if (treeNode.left!=null) {
// 相当于一个map，两个队列同步一起维护节点和路径
nodeArrayList.addLast(treeNode.left);
strings.add(s "->" treeNode.left.val);
}
if (treeNode.right!=null) {
nodeArrayList.addLast(treeNode.right);
strings.add(s "->" treeNode.right.val);
}
}
}
}
return list;
}
}二叉树的所有路径II
dfs
代码语言：javascript复制int sum = 0;
ArrayList<List<Integer>> arrayList = new ArrayList<>();
LinkedList<Integer> list = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
dfs(root,targetSum);
return arrayList;
}
private void dfs(TreeNode root, int targetSum) {
if (root==null) {
return ;
}
// 先序遍历
// 计算当前节点值相加是否等于要找的值
sum =root.val;
list.addLast(root.val);
if (sum==targetSum &&root.left==null && root.right==null) {
arrayList.add(new ArrayList<>(list));
}
// 遍历左树
dfs(root.left,targetSum);
// 遍历右树
dfs(root.right,targetSum);
// 返回上一节点回溯删除当前的总和
Integer integer = list.pollLast();
if (integer!=null){
sum-=integer;
}
}左子树之和
迭代
代码语言：javascript复制/**
* @author ZVerify
* @since 2022/10/31 08:56
* @see <a href="https://leetcode.cn/problems/sum-of-left-leaves/">...</a>
**/
public class 左叶子之和 {
public int sumOfLeftLeaves(TreeNode root) {
if (root==null) return 0;
Deque<TreeNode> list = new LinkedList<>();
list.add(root);
int sum = 0;
while (!list.isEmpty()) {
int size = list.size();
for (int i = 0; i < size; i ) {
TreeNode treeNode = list.pollFirst();
// 如果为当前行的第一个节点，并且左右都为null说明为左叶子
if (i==0 && treeNode.left==null && treeNode.right==null) {
sum =treeNode.val;
}
if (treeNode.left!=null) list.addLast(treeNode.left);
if (treeNode.right!=null) list.addLast(treeNode.right);
}
}
return sum;
}
}找树左下角的值
迭代
代码语言：javascript复制/**
* @author ZVerify
* @since 2022/10/31 09:41
* @see <a href="https://leetcode.cn/problems/find-bottom-left-tree-value/">...</a>
**/
public class 找树左下角的值 {
public int findBottomLeftValue(TreeNode root) {
if (root==null) return 0;
LinkedList<TreeNode> list = new LinkedList<>();
list.add(root);
int value = root.val;
while (!list.isEmpty()) {
int size = list.size();
for (int i = 0; i < size; i ) {
TreeNode node = list.pollLast();
// 直接使用一个变量保存每一层的第一个几点，遍历结束之后一定时最后一层的第一个节点
if (i==0) value = node.val;
if (node.left!=null) list.addLast(node.left);
if (node.right!=null) list.addLast(node.right);
}
}
return value;
}
}合并二叉树
迭代
代码语言：javascript复制/**
* @author ZVerify
* @see <a href="https://leetcode.cn/problems/merge-two-binary-trees/">...</a>
* @since 2022/11/01 11:18
**/
public class 合并二叉树 {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null) return root2;
if(root2==null) return root1;
Deque<TreeNode> list = new LinkedList<>();
list.addLast(root1);
list.addLast(root2);
while (!list.isEmpty()) {
TreeNode left = list.pollFirst();
TreeNode right = list.pollFirst();
// 合并当前节点
left.val = left.val right.val;
// 两个左都不为null，去下一层进行计算
if (left.left != null && right.left != null) {
list.addLast(left.left);
list.addLast(right.left);
}
// 两个右都不为null，去下一层进行计算
if (left.right != null && right.right != null) {
list.addLast(left.right);
list.addLast(right.right);
}
// 左边的左节点为null，右边的左不为null，直接替换，否则为当前值
if (left.left == null && right.left != null) {
left.left = right.left;
}
// 左边的右节点为null，右边的右不为null，直接替换，否则为当前值
if (left.right == null && right.right != null) {
left.right = right.right;
}
}
return root1;
}
}二叉搜索树中的搜索
dfs
代码语言：javascript复制/**
* @author ZVerify
* @since 2022/11/01 15:31
* @see <a href="https://leetcode.cn/problems/search-in-a-binary-search-tree/">...</a>
**/
public class 二叉搜索树中的搜索 {
public TreeNode searchBST(TreeNode root, int val) {
return dfs(root,val);
}
private TreeNode dfs(TreeNode root, int val) {
// 如果为null则为null;
if (root==null) return null;
// 看自己是不是
if (root.val==val) return root;
// 查询左边
TreeNode left = dfs(root.left, val);
// 查询右边
TreeNode right = dfs(root.right, val);
// 左边找到直接返回左边节点
if (left!=null) return left;
// 右边找到直接返回右边节点
if (right!=null) return right;
// 都没有找到的话直接返回null
return null;
}
}验证二叉搜索树
dfs
代码语言：javascript复制/**
* @author ZVerify
* @since 2022/11/01 15:42
* @see <a href="https://leetcode.cn/problems/validate-binary-search-tree/">...</a>
**/
public class 验证二叉搜索树 {
long val = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
return process(root);
}
// 中序遍历
private boolean process(TreeNode root) {
// 为null则为true
if (root==null) return true;
// 左边
boolean left = process(root.left);
// 看当前节点的值有没有前边的值大
if (root.val<=val) return false;
// 替换节点
val = root.val;
// 右边
boolean right = process(root.right);
// 左右都是才是
return left && right;
}
}二叉搜索树的最小绝对值之差
dfs
代码语言：javascript复制/**
* @author ZVerify
* @since 2022/11/01 18:51
* @see <a href="https://leetcode.cn/problems/minimum-absolute-difference-in-bst/submissions/379110665/">...</a>
**/
public class 二叉搜索树的最小绝对差 {
int result = Integer.MAX_VALUE;
int pre = -1;
public int getMinimumDifference(TreeNode root) {
dfs(root);
return result;
}
private void dfs(TreeNode root) {
if (root==null) {
return ;
}
dfs(root.left);
// 初始化根节点
if (pre == -1) {
pre = root.val;
}else {
result = Math.min(Math.abs(root.val-pre),result);
// 更新当前节点给下一节点计算
pre = root.val;
}
dfs(root.right);
}
}二叉树的最近公共祖先
dfs
代码语言：javascript复制/**
* @author ZVerify
* @since 2022/11/02 12:40
* @see <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/submissions/">...</a>
**/
public class 二叉树的最近公共祖先 {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode treeNode = dfs(root,p,q);
if (treeNode==null) return root;
else return treeNode;
}
private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root==null){
return null;
}
TreeNode left = dfs(root.left, p, q);
TreeNode right = dfs(root.right, p, q);
// 当前节点为p或者q直接返回
if (root==q || root==p) {
return root;
}
// 左右都不为null直接返回
if (left!=null && right!=null) return root;
// 在右边找到返回右边的
if (left==null && right!=null) return right;
// 在左边找到返回左边的
if (right==null && left!=null ) return left;
// 所有都不符合返回null
return null;
}
}二叉搜索树中的插入操作
dfs
代码语言：javascript复制/**
* @author ZVerify
* @since 2022/11/02 13:02
* @see <a href="https://leetcode.cn/problems/insert-into-a-binary-search-tree/">...</a>
**/
public class 二叉搜索树中的插入操作 {
public TreeNode insertIntoBST(TreeNode root, int val) {
return dfs(root,val);
}
private TreeNode dfs(TreeNode root, int val) {
// 如果为null则说明到了可以插入的地方了
if (root == null) {
return new TreeNode(val);
}
// 因为是搜索树所以进行搜索遍历
if (root.val<val) {
// 找到插入的值给到当前节点
root.right = dfs(root.right,val);
}else {
root.left = dfs(root.left,val);
}
// 返回当前节点给父节点
return root;
}
}删除二叉搜索树中的节点
dfs
代码语言：javascript复制/**
* @author ZVerify
* @since 2022/11/02 15:01
* @see <a href="https://leetcode.cn/problems/delete-node-in-a-bst/">...</a>
**/
public class 删除二叉搜索树中的节点 {
public TreeNode deleteNode(TreeNode root, int key) {
return dfs(root,key);
}
private TreeNode dfs(TreeNode root, int key) {
if (root==null) return null;
// 搜索树的特性
if (root.val<key) {
root.right = dfs(root.right, key);
} else if (root.val>key) {
root.left = dfs(root.left, key);
}else {
// 现在已经找到了，拿到当前的节点左右节点
TreeNode left = root.left;
TreeNode right = root.right;
// 如果右节点为null则直接返回左节点给上一节点当子节点
if (right == null) return left;
// 如果当前节点存在右节点找到有节点为根节点树的最左节点把左节点放到他左边
while (right!=null && right.left!=null){
right = right.left;
}
right.left = left;
// 完成操作后返回左节点
return right;
}
// 删除完之后返回当前节点给上一节点
return root;
}
}修剪二叉搜索树
dfs
代码语言：javascript复制class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
return bfs(root,low,high);
}
private TreeNode bfs(TreeNode root, int low, int high) {
if (root == null) return null;
if (root.val<low) {
return bfs(root.right,low,high);
}
if (root.val>high) {
return bfs(root.left,low,high);
}
root.left = bfs(root.left,low,high);
root.right = bfs(root.right,low,high);
return root;
}
}把二叉搜索树转为累加数
dfs
利用特性中序遍历，颠倒左右子树遍历顺序
代码语言：javascript复制class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
dfs(root);
return root;
}
private void dfs(TreeNode root) {
if (root == null) return;
dfs(root.right);
root.val = root.val sum;
sum = root.val;
dfs(root.left);
}
}二叉搜索树中的众数
dfs
代码语言：javascript复制/**
* 二叉搜索树中的众数
* @author ZVerify
* @since 2022/11/04 14:48
* @see <a href="https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/">...</a>
**/
public class 二叉搜索树中的众数 {
// 存放结果集
List<Integer> list = new ArrayList<>();
// 双指针的上一节点
TreeNode pre = null;
// 当前节点的出现数量
int count = 0;
// 最大值个数
int maxCount = 0;
public int[] findMode(TreeNode root) {
dfs(root);
return list.stream().mapToInt(a->a).distinct().toArray();
}
private void dfs(TreeNode root) {
if (root==null) return;
dfs(root.left);
// 中序遍历此时处理节点
// 判断是否是初始节点或者一个新的值
if (pre==null || pre.val!=root.val){
count = 1;
}else {
count ;
}
// 如果总数大于了最大出现次数则更新结果集并且更新最大值
if (count>maxCount) {
list.clear();
list.add(root.val);
maxCount=count;
}
// 可能不是一个众数可能包含多个
if (count==maxCount){
list.add(root.val);
}
// 更新当前节点为前置节点
pre = root;
dfs(root.right);
}
}
