力扣hot100刷题笔记——二叉树类型
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
二叉树类型题目
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<Integer> inorderTraversal(TreeNode root) {
/* 1.第一种方案递归
*/
List<Integer> res = new ArrayList<>();
inorderTraversalHelper(root, res);
return res;
}
public void inorderTraversalHelper(TreeNode root, List<Integer> 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<Integer> res = new ArrayList<>();
getNodeValue(root, res);
return check(res);
}
public void getNodeValue(TreeNode root, List<Integer> res) {
if (root == null) {
return;
} else {
getNodeValue(root.left, res);
res.add(root.val);
getNodeValue(root.right, res);
return;
}
}
public boolean check(List<Integer> 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<String> list_word = new LinkedList<String>(Arrays.asList(str_word));
return deserializeHelper(list_word);
}
public TreeNode deserializeHelper(List<String> 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<Integer> res = new ArrayList<>();
HashMap<Integer, Integer> 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<Integer, Integer> 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<Integer> res) {
if (root == null) {
return;
} else {
getList(root.left, res);
res.add(root.val);
getList(root.right, res);
}
}
public void updateList(List<Integer> res, HashMap<Integer, Integer> 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<Integer> 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;
}
}
}