// 前序
// 中序
class Solution {
public List inorderTraversal(TreeNode root) {
List res = new ArrayList<>();
if (root == null) return res;
Deque stack = new ArrayDeque<>();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
p = stack.pop();
res.add(p.val);
p = p.right;
}
}
return res;
}
}
// 后序
// 层序
⭐⭐96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
// 以j作为根，左 [1,j-1]共j-1个元素 右 [j+1, i]共i-j个元素
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
⭐98. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
中序遍历非递归
class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
long last_val = Long.MIN_VALUE;
Deque stack = new LinkedList<>();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
while (p != null) {
stack.push(p);
p = p.left;
}
p = stack.pop();
if (p.val > last_val) {
last_val = p.val;
} else {
return false;
}
p = p.right;
}
return true;
}
}
中序遍历递归
// 递归版本
class Solution {
// 维护一个全局的最小值变量
long min_val = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) return false;
if (root.val <= min_val) return false;
min_val = root.val;
return isValidBST(root.right);
}
}
class Solution {
// 维护一个指向最小值的指针pre
TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) return false;
if (pre != null && root.val <= pre.val) return false;
pre = root;
return isValidBST(root.right);
}
}
递归
class Solution {
public boolean isValidBST(TreeNode root) {
return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean helper(TreeNode root, long lower, long upper) {
if (root == null) return true;
if (root.val > lower && root.val < upper) {
return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
}
return false;
}
}
⭐101. 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
// 递归
class Solution {
public boolean isSymmetric_1(TreeNode root) {
if (root == null) return true;
return helper(root.left, root.right);
}
private boolean helper(TreeNode a, TreeNode b) {
if (a == null && b == null) return true;
if (a == null || b == null || a.val != b.val) return false;
return a.val == b.val && helper(a.left, b.right) && helper(a.right, b.left);
}
}
// 非递归
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
Deque queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode a = queue.poll();
TreeNode b = queue.poll();
if (a == null && b == null) continue;
if (a == null || b == null || a.val != b.val) return false;
queue.offer(a.left);
queue.offer(b.right);
queue.offer(a.right);
queue.offer(b.left);
}
return true;
}
}
102. 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
class Solution {
public List> levelOrder(TreeNode root) {
List> res = new ArrayList<>();
if (root == null) return res;
Deque queue = new ArrayDeque<>();
TreeNode p = root;
queue.offer(p);
while (!queue.isEmpty()) {
int cnt = queue.size();
List temp = new ArrayList<>();
for (int i =0; i < cnt; i++) {
p = queue.poll();
temp.add(p.val);
if (p.left != null) queue.offer(p.left);
if (p.right != null) queue.offer(p.right);
}
res.add(temp);
}
return res;
}
}
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
// 递归
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
// 非递归
class Solution {
public int maxDepth(TreeNode root) {
int depth = 0;
if (root == null) return depth;
Deque queue = new ArrayDeque<>();
TreeNode p = root;
queue.offer(p);
while (!queue.isEmpty()) {
depth++;
int cnt = queue.size();
for (int i = 0; i < cnt; i++) {
p = queue.poll();
if (p.left != null) queue.offer(p.left);
if (p.right != null) queue.offer(p.right);
}
}
return depth;
}
}
105. 从前序与中序遍历序列构造二叉树
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
class Solution {
Map map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode helper(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if ((preorder_left > preorder_right) || (inorder_left > inorder_right)) return null;
TreeNode root = new TreeNode(preorder[preorder_left]);
int inorder_ind = map.get(preorder[preorder_left]);
int left_subtree_size = inorder_ind - 1 - inorder_left + 1, right_subtree_size = inorder_right - (inorder_ind + 1) + 1;
root.left = helper(preorder, inorder, preorder_left + 1, preorder_left + left_subtree_size, inorder_left, inorder_ind - 1);
root.right = helper(preorder, inorder, preorder_right - right_subtree_size + 1, preorder_right, inorder_ind + 1, inorder_right);
return root;
}
}
⭐114. 二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
- 展开后的单链表应该与二叉树 先序遍历 顺序相同。
前序遍历非递归，先记录，后展开 O(n) O(n)
class Solution {
public void flatten_1(TreeNode root) {
if (root == null) return;
List list = new ArrayList<>();
Deque stack = new LinkedList<>();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
while (p != null) {
list.add(p);
stack.push(p);
p = p.left;
}
p = stack.pop();
p = p.right;
}
for (int i = 1; i < list.size(); i++) {
TreeNode prev = list.get(i - 1), cur = list.get(i);
prev.left = null;
prev.right = cur;
}
}
}
前序遍历和展开同步进行 O(n) O(n)
class Solution {
public void flatten_2(TreeNode root) {
if (root == null) return;
Deque stack = new LinkedList<>();
TreeNode p = root;
stack.push(p);
TreeNode prev = null;
while (!stack.isEmpty()) {
p = stack.pop();
if (prev != null) {
prev.left = null;
prev.right = p;
}
prev = p;
if (p.right != null) {
stack.push(p.right);
}
if (p.left != null) {
stack.push(p.left);
}
}
}
}
递归 O(n) O(n)
class Solution {
public void flatten(TreeNode root) {
if(root == null){
return;
}
// 对当前节点的处理
if(root.left != null){
// 找到左子树的最右结点，即root的前驱结点
TreeNode pre = root.left;
while(pre.right != null){
pre = pre.right;
}
pre.right = root.right;
root.right = root.left;
root.left = null;
}
// 任何利用二叉树递归处理问题的算法，归根结底都是对根节点的操作
flatten(root.left);
flatten(root.right);
}
}
寻找前驱节点 O(n) O(1)
class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
TreeNode cur = root;
// root
// -> root.left -> ... -> root.left最右边结点(pre)
// -> root.right -> root.right的子树
while (cur != null) {
if (cur.left != null) {
TreeNode next = cur.left;
TreeNode pre = next;
while (pre.right != null) {
pre = pre.right;
}
pre.right = cur.right;
cur.left = null;
cur.right = next;
}
cur = cur.right;
}
}
}
116. 填充每个节点的下一个右侧节点指针
难度中等713
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
// 层序遍历
class Solution {
public Node connect(Node root) {
if (root == null) return null;
Deque queue= new LinkedList<>();
queue.offer(root);
root.next = null;
while (!queue.isEmpty()) {
int size = queue.size();
Node dummy = new Node();
for (int i = 0; i < size; i++) {
Node p = queue.poll();
if (p.left != null) {
queue.offer(p.left);
dummy.next = p.left;
dummy = dummy.next;
}
if (p.right != null) {
queue.offer(p.right);
dummy.next = p.right;
dummy = dummy.next;
}
}
dummy.next = null;
}
return root;
}
}
// 递归
class Solution {
public Node connect(Node root) {
if (root == null) return root;
if (root.left != null) {
root.left.next = root.right;
root.right.next = root.next == null ? null : root.next.left;
connect(root.left);
connect(root.right);
}
return root;
}
}
226. 翻转二叉树
翻转一棵二叉树。
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
二叉树的最近公共祖先
⭐⭐⭐236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
class Solution {
// 递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null && right == null) return null;
if (left != null && right != null) return root;
return left == null ? right : left;
}
// 存储每个节点的父节点，求得p的所有父节点也即路径，从p到root，然后从q向上遍历得到第一个p遍历过的节点
// 很慢
public TreeNode lowestCommonAncestor_1(TreeNode root, TreeNode p, TreeNode q) {
Map parent = new HashMap<>();
Set visited = new HashSet<>();
dfs(root, parent);
while (p != null) {
visited.add(p.val);
p = parent.get(p.val);
}
while (q != null) {
if (visited.contains(q.val)) return q;
q = parent.get(q.val);
}
return null;
}
private void dfs(TreeNode root, Map parent) {
if (root.left != null) {
parent.put(root.left.val, root);
dfs(root.left, parent);
}
if (root.right != null) {
parent.put(root.right.val, root);
dfs(root.right, parent);
}
}
}
⭐235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
public TreeNode lowestCommonAncestor_1(TreeNode root, TreeNode p, TreeNode q) {
while (true) {
if (root.val > p.val && root.val > q.val) {
root = root.left;
} else if (root.val < p.val && root.val < q.val) {
root = root.right;
} else {
return root;
}
}
}
}
路径总和
⭐112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
// 递归，递归边界为剩余为0
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null && root.val == targetSum) return true;
return hasPathSum(root.left, targetSum - root.val)
|| hasPathSum(root.right, targetSum - root.val);
}
}
⭐113. 路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
// dfs，如果到叶子结点路径和等于target则将当前路径放入结果集中
class Solution {
public List> pathSum(TreeNode root, int targetSum) {
List> res = new ArrayList<>();
List path = new ArrayList<>();
dfs(root, targetSum, path, res);
return res;
}
private void dfs(TreeNode root, int targetSum, List path, List> res) {
if (root == null) return;
path.add(root.val);
targetSum -= root.val;
if (root.left == null && root.right == null && targetSum == 0) {
res.add(new ArrayList<>(path));
}
dfs(root.left, targetSum, path, res);
dfs(root.right, targetSum, path, res);
path.remove(path.size() - 1);
targetSum += root.val;
}
}
⭐⭐437. 路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
// 对每个结点向下进行dfs，如果路径等于target将结果加1
class Solution {
// 双重递归
public int pathSum(TreeNode root, int targetSum) {
if (root == null) return 0;
int res = rootSum(root, targetSum);
res += pathSum(root.left, targetSum);
res += pathSum(root.right, targetSum);
return res;
}
// 从root往下遍历得到路径和为target的路径数量
private int rootSum(TreeNode root, int targetSum) {
if (root == null) return 0;
int res = 0;
int val = root.val;
if (val == targetSum) res++;
res += rootSum(root.left, targetSum - val);
res += rootSum(root.right, targetSum - val);
return res;
}
}
// 前缀和
class Solution {
Map map = new HashMap<>();
int res = 0;
public int pathSum(TreeNode root, int targetSum) {
if (root == null) return res;
map.put(0, 1);
dfs(root, 0, targetSum);
return res;
}
private void dfs(TreeNode root, int curSum, int targetSum) {
if (root == null) return;
curSum += root.val;
if (map.containsKey(curSum - targetSum)) {
res += map.get(curSum - targetSum);
}
map.put(curSum, map.getOrDefault(curSum, 0) + 1);
dfs(root.left, curSum, targetSum);
dfs(root.right, curSum, targetSum);
map.put(curSum, map.getOrDefault(curSum, 0) - 1);
}
}
二叉树路径系列
543. 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
class Solution {
int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) return 0;
getDepth(root);
return res;
}
// 对于每个结点root为中心，计算最长路径，从root往左高度 + 从root往右的高度
// 返回以root为根的树的高度，也就是 max(从root往左高度，从root往右的高度)
private int getDepth(TreeNode root) {
if (root == null) return 0;
int left = root.left == null ? 0 : getDepth(root.left) + 1;
int right = root.right == null ? 0 : getDepth(root.right) + 1;
res = Math.max(res, left + right);
return Math.max(left ,right);
}
}
124. 二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
class Solution {
int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return res;
}
// dfs返回以root为根往一边走所能得到的最大路径
private int dfs(TreeNode root) {
if (root == null) return 0;
int leftSum = Math.max(0, dfs(root.left)); // 如果左右孩子的结果是负数的话就舍弃。
int rightSum = Math.max(0, dfs(root.right));
res = Math.max(res, leftSum + rightSum + root.val);
return Math.max(leftSum, rightSum) + root.val;
}
}
class Solution {
private int pathSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return pathSum;
}
// dfs(node):表示从node结点开始往某个方向所能抵达路径的最大值
// 那么可以两边都不走，可以从node往左走，可以从node往右走
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left);
int right = dfs(node.right);
// 当前节点有四个选择：
// 1）独立成线，直接返回自己的值
// 2）跟左子节点合成一条路径
// 3）跟右子节点合成一条路径
int res = Math.max(node.val, node.val + Math.max(left, right));
// 4）以自己为桥梁，跟左、右子节点合并成一条路径
pathSum = Math.max(pathSum, Math.max(res, node.val + left + right));
return res;
}
}
687. 最长同值路径
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
class Solution {
int res = 0;
public int longestUnivaluePath(TreeNode root) {
if (root == null) return 0;
dfs(root);
return res;
}
private int dfs(TreeNode root) {
if (root == null) return 0;
int left = root.left == null ? 0 : 1 + dfs(root.left);
int right = root.right == null ? 0 : 1 + dfs(root.right);
// 如果当前节点和孩子节点不同值，就把边长重新赋值为0。
if (left > 0 && root.left.val != root.val) {
left = 0;
}
if (right > 0 && root.right.val != root.val) {
right = 0;
}
res = Math.max(res, left + right);
return Math.max(left, right);
}
}
树的序列化
⭐⭐297. 二叉树的序列化与反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
DFS：
public class Codec {
// 用 # 来表示null结点
// dfs
// serialize 1 2 # # 3 4 5
// deserialize
// 1 | 2 # # | 3 4 5
public static final String NULL_VAL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return NULL_VAL;
return root.val + " " + serialize(root.left) + " " + serialize(root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque strs = new LinkedList<>(Arrays.asList(data.split(" ")));
return dfs(strs);
}
private TreeNode dfs(Deque strs) {
String str = strs.poll();
if (NULL_VAL.equals(str)) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(str));
root.left = dfs(strs);
root.right = dfs(strs);
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));
BFS：
public class Codec {
// serialize: 层序遍历存储val值，null的记录为特殊字符
// 1 | 2 3 | null null 4 5
// deserialize: 新建一个queue用来做层序遍历，对于pop出来结点如果他有孩子则要将孩子入队继续操作
// 每次获取结点从层序序列中获取
public static final String NULL_VAL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return NULL_VAL;
StringBuilder sb = new StringBuilder();
Deque queue = new LinkedList<>();
TreeNode p = root;
queue.offer(p);
while (!queue.isEmpty()) {
p = queue.pop();
if (p != null) {
sb.append(p.val + " ");
queue.offer(p.left);
queue.offer(p.right);
} else {
sb.append(NULL_VAL + " ");
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.trim() == NULL_VAL) return null;
Deque strs = new LinkedList<>(Arrays.asList(data.split(" ")));
Deque queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(strs.poll()));
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
String left = strs.poll();
String right = strs.poll();
if (!NULL_VAL.equals(left)) {
node.left = new TreeNode(Integer.parseInt(left));
queue.offer(node.left);
}
if (!NULL_VAL.equals(right)) {
node.right = new TreeNode(Integer.parseInt(right));
queue.offer(node.right);
}
}
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));
⭐652. 寻找重复的子树
给定一棵二叉树 root，返回所有重复的子树。
对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
class Solution {
public static final String NULL_VAL = "#";
Map map = new HashMap<>();
List res = new ArrayList<>();
public List findDuplicateSubtrees(TreeNode root) {
serialize(root);
return res;
}
private String serialize(TreeNode root) {
if (root == null) return NULL_VAL;
String str = root.val + " " + serialize(root.left) + " " + serialize(root.right);
map.put(str, map.getOrDefault(str, 0) + 1);
if (map.get(str) == 2) {
res.add(root);
}
return str;
}
}
⭐449. 序列化和反序列化二叉搜索树
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
Solution1: 二叉搜索树也是二叉树，因此可以和 lc297 一样做
Solution2：前序遍历，然后将序列排序得到中序遍历序列，然后根据前序序列+中序序列构造二叉树
public class Codec {
public static final String NULL_VAL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return NULL_VAL;
return root.val + " " + serialize(root.left) + " " + serialize(root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque queue = new LinkedList<>(Arrays.asList(data.split(" ")));
return dfs(queue);
}
private TreeNode dfs(Deque queue) {
String str = queue.poll();
if (NULL_VAL.equals(str)) return null;
TreeNode root = new TreeNode(Integer.parseInt(str));
root.left = dfs(queue);
root.right = dfs(queue);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;
