Поиск в бинарном дереве поиска вручную

Это 9-й день моего участия в августовском испытании обновлений.Подробности о мероприятии:Испытание августовского обновления

Всем привет,сегодня 9-й день моего участия в августовском обновлении.Алгоритмическая проблема,связанная с бинарным деревом,которую я приношу вам сегодня,это поиск в бинарном дереве поиска.Текст следующий:

тема:

Дан корневой узел двоичного дерева поиска (BST) и значение. Вам нужно найти узел в BST, значение узла которого равно заданному значению. Возвращает поддерево с корнем в этом узле. Возвращает NULL, если узел не существует.

Например:

Вы должны вернуть поддерево следующим образом:

В приведенном выше примере, если искомое значение равно 5, но поскольку нет узла со значением 5, мы должны вернуть NULL.

Идеи решения проблем

Рекурсивная реализация очень проста:

• Если корневой узел пустой root == null или значение корневого узла равно искомому значению val == root.val, вернуть корневой узел.

• Если val

• Если val > root.val, введите правое поддерево корневого узла и выполните поиск searchBST(root.right, val).

• Вернуть корневой узел.

Код

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // 利用BST左小右大的特点，不断递归搜索两边
        if (root == null || root.val == val) return root;
        return val < root.val? searchBST(root.left, val) : searchBST(root.right, val); 
    }
}

наконец

Анализ сложности

• Временная сложность: O(h), где h — высота дерева. Средняя временная сложность — O(logN), а наихудшая временная сложность — O(N).

• Пространственная сложность: O(h), глубина рекурсивного стека равна h. Глубина составляет O(logN) в среднем случае и O(N) в худшем случае.