700. 二叉搜索树中的搜索
?做题思路or感想:
- 递归参数:一个遍历节点,一个比较节点值的val
- 递归中止条件:
cur == nullptr
为止,即是节点遍历到了头 - 单层递归逻辑:比较节点值和目标值
- 如果相等,则给预设的节点赋值
- 如果大了,就往左节点走
- 如果小了,就往右节点走
- 最后在主函数返回预设节点
class Solution {
public:
TreeNode* result = nullptr; //预设一个全局节点
void dfs(TreeNode* cur, int val) {
if (cur == nullptr)return; //中止条件
//三种情况的处理
if (cur->val == val) {
result = cur;
return;
}
if (cur->val > val)dfs(cur->left, val);
if (cur->val < val)dfs(cur->right, val);
}
TreeNode* searchBST(TreeNode* root, int val) {
dfs(root, val);
return result;
}
};