LeetCode700:二叉搜索树中的搜索算法解析

问题描述

给定一个二叉搜索树（Binary Search Tree）和一个目标值，编写一个函数来查找该目标值对应的节点。如果树中存在该目标值，则返回对应的节点；否则返回空。

解决方案

二叉搜索树的特点是左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。基于这一特性，我们可以通过递归或迭代的方式进行搜索。本文采用迭代方法，使用队列来辅助遍历树结构。

代码实现

/**
 * 定义二叉树节点结构
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX_SIZE 5000
struct TreeNode* searchBST(struct TreeNode* root, int targetVal)
{
    if (!root) return NULL; // 如果根节点为空，直接返回NULL
    struct TreeNode* queue[MAX_SIZE]; // 定义队列用于存储待处理的节点
    int frOnt= -1, rear = -1; // 初始化队列的前指针和后指针
    queue[++rear] = root; // 将根节点入队
    while (front         struct TreeNode* currentNode = queue[++front]; // 取出队首元素
        if (currentNode->val == targetVal) { // 如果当前节点值等于目标值，返回当前节点
            return currentNode;
        }
        if (currentNode->left) { // 如果当前节点有左子节点，将左子节点入队
            queue[++rear] = currentNode->left;
        }
        if (currentNode->right) { // 如果当前节点有右子节点，将右子节点入队
            queue[++rear] = currentNode->right;
        }
    }
    return NULL; // 遍历完整棵树未找到目标值，返回NULL
}