算法训练-搜索

搜索

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和q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 递归查找右子树中的p和q
        TreeNode 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; // 初始化k
        inorder(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; // 返回等于基准的值
        }
    }
}