二叉树_二叉搜索树中的搜索
- 一、leetcode-700
- 二、题解
- 1.引库
- 2.代码
一、leetcode-700
二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]
二、题解
1.引库
#include <iostream>#include <cstdio>#include <cstdlib>#include <queue>#include <stack>#include <algorithm>#include <string>#include <map>#include <set>#include <vector>using namespace std;2.代码
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root==NULL||root->val==val) return root;if(val<root->val) return searchBST(root->left,val);else return searchBST(root->right,val);}
};
对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。
对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。
例如要搜索元素为3的节点，我们不需要搜索其他节点，也不需要做回溯，查找的路径已经规划好了。
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while(root!=NULL){if(root->val==val) return root;else if(val<root->val) root=root->left;else root=root->right;}return NULL;}
};
