算法学习笔记（六）：二叉树一创建、插入、删除、BFS
一.最近公共祖先
1.二叉搜索树的最近公共祖先
给定一个二叉搜索树，找到该树种两个指定节点的最近公共祖先
公共祖先定义：对于有根树 T 的两个节点p、q，最近公共祖先表示为一个节点x，满足x
是p、q的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
/**
首先定义了二叉搜索树，那么二叉搜索树具有左节点<root<右节点
而自己也可以是自己的祖先，所以思路：
1.首先判断p、q和根节点比较大小
2.如果p、q都大于root，那么只能去右子树去找
3.如果p、q都小于root，那么去左子树找
4.如果一大一小，那么当前root节点肯定就是最近公共祖先
直接返回root即可
*/
//本题不需要判空，因为题目要求p、q一定在树中
//而且只有节点在左\右子树中才会去递归，不在就直接返回root了
int val = root.val;
if (val > p.val && val > q.val) {
//在左子树中
return lowestCommonAncestor(root.left, p, q);
}
if (val <p.val && val < q.val) {
//在右子树中
return lowestCommonAncestor(root.right, p, q);
}
//一左一右
return root;
}
}2.二叉树的最近公共祖先
给定一个二叉树，找到该树中两个指定节点的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
/**
该题目明确p、q一定会在树中，那么就有几种情况
1.p、q分别在root的左右子树中，就是当前节点的左右子树中各有其中一个
那么这个情况下，当前节点就是最近公共祖先
2.p、q都在同一侧子树中，要么都在左子树中，要么都在右子树中
这个情况下，只要先找到p或者q，那么递归结束，因为p或者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) return right;
//如果右边没找到 那么肯定在另一边
if (right == null) return left;
//最后在两边找到了 那么当前root就是
return root;
}
}二.二叉搜索树
1.验证二叉搜索树
给你一个二叉树的根节点 root，判断是否是一个有效的二叉搜索树
二叉搜索树定义：
- 节点的左子树只包含小于当前节点的数
- 节点的右子树只包含大于当前节点的数
- 所有左子树和右子树自身必须也是二叉搜索树
class Solution {
public boolean isValidBST(TreeNode root) {
//其实就是递归二叉树 然后判断左是否<root<右即可
//要用long，否则有可能节点值正好是int的最大最小值
return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean dfs(TreeNode root, long left, long right) {
if (root == null) return true;
long val = root.val;
return left < val && val < right
&& dfs(root.left, left, val)
&& dfs(root.right, val, right);
}
}三.创建二叉树
1.将有序数组转换成二叉搜索树
给你一个整数数组 nums，其中元素以及按照 升序 排序，请你将其转换为一棵
平衡 二叉搜索树。
平衡：是指所有节点的左右子树深度相差不超过 1
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
//这个好办，因为数组以及排好序了
//首先搜索树是左<root<右 而平衡是所有节点深度差不超过1
//所以一层一层构建过去就行，最多相差1
//我们将数组从中间节点一分为2
//前半段构建左子树 后半段构建右子树 然后递归构建
return dfs(nums, 0, nums.length);
}
public TreeNode dfs(int[] nums, int left, int right) {
if (left == right) return null;
//找到中间节点 无符号右移1位 就相当于除以2
int mid = (left + right) >>> 1;
return new TreeNode(nums[mid], dfs(nums, left, mid), dfs(nums, mid + 1, right));
}
}2.最大二叉树
给定一个不重复的整数数组 nums，最大二叉树 可以用下面的算法从 nums递归构建
- 创建一个根节点，其值为 nums 中的最大值
- 递归的在最大值 左边 的子数组前缀上构建左子树
- 递归的在最大值右边的子数组后缀上构建右子树
返回 nums 构建后的 最大二叉树
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
/**
和排好序的数组构建一样 只不过这次是未排序的数组
以及构建一个普通的二叉树 只是要求root需要为最大值
那么每次就以最大值为root 找出最大值的index即可
*/
return dfs(nums, 0, nums.length);
}
private TreeNode dfs(int[] nums, int left, int right) {
if (left == right) return null;
//找出最大值
int max = left;
for (int i = left; i < right; i++) {
if (nums[i] > nums[max]) max = i;
}
//以max为root分成左右构建左右子树
return new TreeNode(nums[max], dfs(nums, left, max), dfs(nums, max + 1, right));
}
}3.从前序与中序遍历序列构建二叉树
给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的前序遍历，inorder 是同一
棵树的中序遍历，请够造二叉树并返回其根节点。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
/**
前序+中序可以确定一个二叉树 前序的第一个元素肯定就是根节点
然后从preorder第一个元素获取在inorder中的index
中序LNR可知，在第一个元素位置左边的肯定是左子树 在右边的肯定是右子树
然后就可以确定了树的根节点以及左右子树的范围
然后拿到inorder的左子树范围去pre中确定范围
先确定左子树在前序遍历中的范围，然后这个范围内的第一个元素就是左子树的跟节点
同理右子树在前序遍历中的范围 第一个元素就是右子树的根节点
然后递归构建就是了
*/
//首先用哈希表存储中序数组元素的index 前提是数组内元素都是无重复的
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
//递归构建 根节点以及左右子树的两边边界index
return dfs(preorder, 0, preorder.length, inorder, 0, inorder.length, map);
}
public TreeNode dfs(int[] preorder, int preL, int preR,
int[] inorder, int inL, int inR, Map<Integer, Integer> map) {
if (preL == preR) return null;
//前序遍历中的第一个元素肯定是root节点
//那么就拿前序遍历中的第一个元素去中序中找位置
//找到之后，该位置之前都是左子树，之后都是右子树
int leftSize = map.get(preorder[preL]) - inL;
//pre+1 因为已经用掉了第一个元素用来构建root 从pre+1开始递归后面的
TreeNode left = dfs(preorder, preL + 1, preL + 1 + leftSize, inorder, inL, inL + leftSize, map);
//inL + 1的概念是 算右子树范围肯定是左子树范围+根节点本身就是右子树的left起点
TreeNode right = dfs(preorder, preL + 1 + leftSize, preR, inorder, inL + 1 + leftSize, inR, map);
return new TreeNode(preorder[preL], left, right);
}
}4.从中序与后续遍历序列够造二叉树
给定两个整数数组 inorder 和 postorder，其中 inorder 是中序遍历，postorder是后续遍历
请你够造并返回二叉树
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
//中序+后续确定一棵二叉树
//postorder的最后一个元素是根节点
//然后拿这个元素去中序里面确定根节点的位置
//然后中序根节点之前是左子树 之后是右子树
//然后就是一个和原问题一样的子问题，递归构建
//然后其他逻辑跟前中序是一个逻辑 因为在inorder里面左子树的范围是一样的
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return dfs(postorder, 0, postorder.length, inorder, 0, inorder.length, map);
}
public TreeNode dfs(int[] postorder, int postL, int postR,
int[] inorder, int inL, int inR, Map<Integer, Integer> map) {
if (postL == postR) return null;
int leftSize = map.get(postorder[postR - 1]) - inL;
TreeNode left = dfs(postorder, postL, postL + leftSize, inorder, inL, inL + leftSize, map);
TreeNode right = dfs(postorder, postL + leftSize, postR - 1, inorder, inL + 1 + leftSize, inR, map);
return new TreeNode(postorder[postR - 1], left, right);
}
}四.插入/删除节点
1.二叉搜索树中的插入操作
给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value，将值插入二叉搜索树，返回
插入后二叉搜索树的根节点，输入数据保证，新值和原始二叉搜索树中任意节点值不同
注意：可能存在多种有效的插入方式，返回任意有效结果即可
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
/**
首先是二叉搜索树 那么满足 L < N < R
所以判断插入值和当前root的大小关系
大于当前值 插入到右子树中去
一直遍历，
小于当前值 插入到左子树中去
*/
if (root == null) return new TreeNode(val);
dfs(root, val);
//循环解法
// TreeNode cur = root;
// while (cur != null) {
// if (cur.val < val) {
// //右
// if (cur.right == null) {
// cur.right = new TreeNode(val);
// break;
// }
// cur = cur.right;
// } else {
// //左
// if (cur.left == null) {
// cur.left = new TreeNode(val);
// break;
// }
// cur = cur.left;
// }
// }
return root;
}
private void dfs(TreeNode root, int val) {
if (root == null) return;
//判断是要插入到左子树还是右子树
if (root.val > val) {
//左
if (root.left == null) {
root.left = new TreeNode(val);
return;
}
dfs(root.left, val);
} else {
//右
if (root.right == null) {
root.right = new TreeNode(val);
return;
}
dfs(root.right, val);
}
}
}五.BFS
1. 二叉树的层序遍历
给你二叉树的根节点 root，返回其节点值的 层序遍历
层序遍历就是逐层地从左到右访问所有节点
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
/**
层序遍历 就是把同一深度的所有节点从左到右顺序输出
核心是先进先出 用队列， 然后用当前队列的长度控制遍历队列的次数
这样从队列拿到的数据就是当前深度的所有节点
首先将root根节点放到队列中去，然后遍历，外部循环判断队列不为空就继续遍历
然后内部进行内循环，循环长度就是当前队列的size 然后循环内部进行判断，有子节点就放到
队列中去，内循环结束，就表示这一层节点遍历完了，就将数据放到list中去
比如：假设当前二叉树是个满二叉树，深度是3，也就是说每个节点都会有左右子节点
第一次循环是循环一次，然后此时，队列循环了一次拿走了根节点，然后放入了根节点的2个子节点
队列size是2，然后继续循环，循环次数是2，然后每个节点又有2个子节点，此时循环2次结束之后
队列size是4，然后循环了2次就将上一层级的节点都拿走了，依次类推，
下一次循环4次，结束时队列中就有8个节点
因为深度是3 这一层级的节点都没有子节点，循环8次之后队列中就没数据了
就退出外循环了
这种算法就是广度优先
*/
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
LinkedList<TreeNode> queue = new LinkedList<>();
//根节点入队
queue.add(root);
//遍历队列
while (!queue.isEmpty()) {
List<Integer> list = new ArrayList<>();
//记录当前queue size 用作内循环
int size = queue.size();
while (size-- > 0) {
//出先进的节点
TreeNode node = queue.poll();
//随后将出的节点的左右孩子节点放入queue
list.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
result.add(list);
}
return result;
}
}