一.最近公共祖先

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位 就相当于除以2int 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);}//递归构建 根节点以及左右子树的两边边界indexreturn 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();//随后将出的节点的左右孩子节点放入queuelist.add(node.val);if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}result.add(list);}return result;}
}