搜索
leetcode102. 二叉树的层序遍历
法一：广度优先遍历
leetcode103. 二叉树的锯齿形层序遍历
法一：双端队列
法二：倒序
法三：奇偶逻辑分离
leetcode236. 二叉树的最近公共祖先
法一：递归
leetcode230. 二叉搜索树中第 K 小的元素
法一：中序遍历
leetcode235. 二叉搜索树的最近公共祖先
法一：递归
法二：迭代
leetcode215. 数组中的第K个最大元素
法一：快速排序
leetcode102. 二叉树的层序遍历
102. 二叉树的层序遍历
https://leetcode.cn/problems/binary-tree-level-order-traversal/
法一：广度优先遍历
public class Method01 {public List<List<Integer>> levelOrder(TreeNode root) {// 创建一个队列，用于存储当前层的节点，以实现层序遍历Queue<TreeNode> queue = new LinkedList<>();// 创建一个列表，用于存放每一层的结果List<List<Integer>> result = new LinkedList<>();// 如果根节点不为空，将其加入队列if (root != null) {queue.offer(root);}// 进行层序遍历，只要队列不为空，就继续循环while (!queue.isEmpty()) {// 创建一个列表用于存储当前层的节点值List<Integer> level = new LinkedList<>();// 遍历当前层的所有节点for (int i = queue.size(); i > 0; i--) {// 从队列中取出一个节点TreeNode node = queue.poll();// 将当前节点的值加入到该层结果列表中level.add(node.val);// 将当前节点的左子节点加入队列（如果存在）if (node.left != null) {queue.offer(node.left);}// 将当前节点的右子节点加入队列（如果存在）if (node.right != null) {queue.offer(node.right);}}// 将当前层的节点值列表添加到结果中result.add(level);}// 返回最终的结果列表，其中包含每一层的节点值return result;}
}
leetcode103. 二叉树的锯齿形层序遍历
103. 二叉树的锯齿形层序遍历https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
法一：双端队列
public class Method01 {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {// 创建一个队列用于存储节点，以便实现层序遍历Queue<TreeNode> queue = new LinkedList<>();// 创建一个列表用于存放每一层的结果List<List<Integer>> result = new LinkedList<>();// 如果根节点不为空，将其加入队列if (root != null) {queue.offer(root);}// 进行层序遍历，只要队列不为空，就继续循环while (!queue.isEmpty()) {// 创建一个双端链表用于存储当前层的节点值LinkedList<Integer> level = new LinkedList<>();// 遍历当前层的所有节点for (int i = queue.size(); i > 0; i--) {// 从队列中取出一个节点TreeNode node = queue.poll();// 根据当前层是偶数层还是奇数层来决定添加节点值的位置if (result.size() % 2 == 0) {// 如果是偶数层，从尾部添加节点值level.addLast(node.val);} else {// 如果是奇数层，从头部添加节点值level.addFirst(node.val);}// 将当前节点的左子节点加入队列（如果存在）if (node.left != null) {queue.offer(node.left);}// 将当前节点的右子节点加入队列（如果存在）if (node.right != null) {queue.offer(node.right);}}// 将当前层的节点值列表添加到结果中result.add(level);}// 返回最终的结果列表return result;}
}
法二：倒序
public class Method02 {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {// 创建一个队列，用于存储即将被访问的节点，以实现层序遍历Queue<TreeNode> queue = new LinkedList<>();// 创建一个列表，用于存放每一层的结果List<List<Integer>> result = new LinkedList<>();// 如果根节点不为空，将其加入队列if (root != null) {queue.offer(root);}// 进行层序遍历，只要队列不为空，就继续循环while (!queue.isEmpty()) {// 创建一个列表用于存储当前层的节点值List<Integer> level = new LinkedList<>();// 遍历当前层的所有节点for (int i = queue.size(); i > 0; i--) {// 从队列中取出一个节点TreeNode node = queue.poll();// 将当前节点的值加入到该层结果列表中level.add(node.val);// 将当前节点的左子节点加入队列（如果存在）if (node.left != null) {queue.offer(node.left);}// 将当前节点的右子节点加入队列（如果存在）if (node.right != null) {queue.offer(node.right);}}// 如果当前层是奇数层，则反转层的顺序if (result.size() % 2 == 1) {Collections.reverse(level);}// 将当前层的节点值列表添加到结果中result.add(level);}// 返回最终的结果列表，其中包含每一层的节点值return result;}
}
法三：奇偶逻辑分离
public class Method03 {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {// 创建一个双端队列用于存储节点Deque<TreeNode> queue = new LinkedList<>();// 创建一个结果列表用于存储每一层的节点值List<List<Integer>> result = new LinkedList<>();// 如果根节点不为空，则将其加入队列if (root != null) {queue.offer(root);}// 只要队列不为空，就继续处理while (!queue.isEmpty()) {// 创建一个当前层的节点值列表List<Integer> level = new LinkedList<>();// 从左到右遍历当前层的节点for (int i = queue.size(); i > 0; i--) {// 获取并移除队列的头部节点TreeNode node = queue.poll();level.add(node.val); // 将节点值添加到当前层列表中// 如果左子节点不为空，则加入队列if (node.left != null) {queue.offer(node.left);}// 如果右子节点不为空，则加入队列if (node.right != null) {queue.offer(node.right);}}// 将当前层的节点值列表添加到结果中result.add(level);// 检查队列是否为空，如果不为空，则处理下一层if (!queue.isEmpty()) {// 创建一个新的当前层的节点值列表level = new LinkedList<>();// 从右到左遍历当前层的节点for (int i = queue.size(); i > 0; i--) {// 获取并移除队列的尾部节点TreeNode node = queue.pollLast();level.add(node.val); // 将节点值添加到当前层列表中// 如果右子节点不为空，则加入队列的头部if (node.right != null) {queue.offerFirst(node.right);}// 如果左子节点不为空，则加入队列的头部if (node.left != null) {queue.offerFirst(node.left);}}// 将当前层的节点值列表添加到结果中result.add(level);}}// 返回最终的结果return result;}
}
leetcode236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
法一：递归
public class Method01 {// 找到二叉树中两个节点的最近公共祖先public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 如果当前节点为空，或者当前节点是p或q，则返回当前节点if (root == null || root.val == p.val || root.val == q.val) {return root;}// 递归查找左子树中的p和qTreeNode left = lowestCommonAncestor(root.left, p, q);// 递归查找右子树中的p和qTreeNode right = lowestCommonAncestor(root.right, p, q);// 如果左子树没有找到，则返回右子树的结果if (left == null) {return right;}// 如果右子树没有找到，则返回左子树的结果if (right == null) {return left;}// 如果左右子树都找到了p和q，说明当前节点是最近公共祖先return root;}
}
leetcode230. 二叉搜索树中第 K 小的元素
230. 二叉搜索树中第 K 小的元素https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
法一：中序遍历
public class Method01 {int k, res; // k为要查找的第k小元素，res为结果// 主方法：找到二叉搜索树中第k小的元素public int kthSmallest(TreeNode root, int k) {this.k = k; // 初始化kinorder(root); // 进行中序遍历return res; // 返回结果}// 中序遍历方法public void inorder(TreeNode root) {if (root == null) return; // 如果节点为空，直接返回inorder(root.left); // 递归遍历左子树if (k == 0) {return; // 如果k已经为0，说明已经找到第k小元素，直接返回}if (--k == 0) { // 访问当前节点res = root.val; // 更新结果为当前节点的值}inorder(root.right); // 递归遍历右子树}
}
leetcode235. 二叉搜索树的最近公共祖先
235. 二叉搜索树的最近公共祖先https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
法一：递归
public class Method01 {// 找到二叉搜索树中两个节点的最近公共祖先public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 判断当前节点是否在p和q之间if ((root.val >= p.val && root.val <= q.val) || (root.val <= p.val && root.val >= q.val)) {return root; // 当前节点是最近公共祖先}// 如果当前节点的值小于p的值，说明p和q在右子树中if (root.val < p.val) {return lowestCommonAncestor(root.right, p, q);} else { // 否则，p和q在左子树中return lowestCommonAncestor(root.left, p, q);}}
}法二：迭代
public class Method02 {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while (root!= null){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;}}return null;}
}
leetcode215. 数组中的第K个最大元素
215. 数组中的第K个最大元素https://leetcode.cn/problems/kth-largest-element-in-an-array/
法一：快速排序
public class Method01 {// 查找数组中第 k 大的元素public int findKthLargest(int[] nums, int k) {// 选择数组中间的元素作为基准int num = nums[nums.length / 2];// 创建三个列表来存储大于、小于和等于基准的元素ArrayList<Integer> maxList = new ArrayList<>(); // 大于基准的元素ArrayList<Integer> minList = new ArrayList<>(); // 小于基准的元素ArrayList<Integer> equalList = new ArrayList<>(); // 等于基准的元素// 遍历数组，分类存储元素for (int i = 0; i < nums.length; i++) {if (nums[i] > num) {maxList.add(nums[i]); // 大于基准，添加到 maxList} else if (nums[i] < num) {minList.add(nums[i]); // 小于基准，添加到 minList} else {equalList.add(nums[i]); // 等于基准，添加到 equalList}}// 如果 k 小于等于最大元素集合的大小，递归查找if (k <= maxList.size()) {int arr[] = new int[maxList.size()]; // 创建数组保存 maxList 的元素for (int i = 0; i < maxList.size(); i++) {arr[i] = maxList.get(i); // 将 maxList 的元素复制到数组}return findKthLargest(arr, k); // 递归查找第 k 大的元素}// 如果 k 大于最大元素集合加上等于基准的元素数量else if (k > maxList.size() + equalList.size()) {int arr[] = new int[minList.size()]; // 创建数组保存 minList 的元素for (int i = 0; i < minList.size(); i++) {arr[i] = minList.get(i); // 将 minList 的元素复制到数组}return findKthLargest(arr, k - maxList.size() - equalList.size()); // 递归查找}// 否则，返回基准值else {return num; // 返回等于基准的值}}
}
