700. 二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如，
给定二叉搜索树: 4 / \ 2 7 / \ 1 3 和值: 2 你应该返回如下子树: 2 / \ 1 3
方法一:递归
TreeNode* searchBST(TreeNode* root, int val) { //确定结束条件:root为null,或者root->val ==val; //否则,根据val和 root->val的大小情况,决定是向左进行搜索还是向右进行搜索. if(root==NULL||root->val==val) { return root; } if(root->val > val) { return searchBST(root->left,val);//找到之后需要进行返回,所以得有return } if(root->val < val) { return searchBST(root->right,val); } return NULL;//为啥这里一定要返回NULL呢,感觉没必要吧... }
方法二迭代
TreeNode* searchBST(TreeNode* root, int val) { while(root!=NULL) { if(root->val > val) { return searchBST(root->left,val);//找到之后需要进行返回,所以得有return } else if(root->val < val) { return searchBST(root->right,val); } else { return root; } } return NULL; }
701. 二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1：
输入：root = [4,2,7,1,3], val = 5 输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：
示例 2：
输入：root = [40,20,60,10,30,50,70], val = 25 输出：[40,20,60,10,30,50,70,null,null,25]
示例 3：
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 输出：[4,2,7,1,3,5]
方法一递归法:
//递归法 TreeNode* insertIntoBST(TreeNode* root, int val) { //当该节点为空,说明可以在此处插入节点了.创建节点,存入值,并返回. if(root==NULL){ TreeNode* node = new TreeNode(val); return node; } if(root->val > val){//每次接收传 返回的节点指针.. root->left = insertIntoBST(root->left,val); } if(root->val < val){ root->right = insertIntoBST(root->right,val); } return root;//如果等于,则不做插入,直接返回... }
方法二:无返回值的递归法
TreeNode* parent; void traversal(TreeNode* cur,int val) { if(cur==NULL) { //此处可以插入val TreeNode* node = new TreeNode(val); //根据当前值和上一个节点的值的大小,来决定插入左子树,还是右子树 if(parent->val > val) { parent->left = node; } else { parent->right = node; } return; } parent = cur;//parent进行更新 if(val < cur->val) { traversal(cur->left,val); } if(val > cur->val) { traversal(cur->right,val); } return; } //无返回值的递归法 TreeNode* insertIntoBST(TreeNode* root, int val) { if(root==NULL) { root = new TreeNode(val); } parent = new TreeNode(val);//把当前节点存一份,当成前一个节点.... traversal(root,val); return root; }
方法三:迭代法
//迭代 TreeNode* insertIntoBST(TreeNode* root, int val) { if(root==NULL) { root = new TreeNode(val); } TreeNode* parent = new TreeNode(val); TreeNode* cur = root; while(cur!=NULL) { //更新parent 这个一定要放在while的最前面,因为后面cur就会被更新了. parent = cur; if(val < cur->val) { cur = cur->left; } else if(val > cur->val) { cur = cur->right; } else { //如果相等,则说明val节点已经存在,则直接返回该树. return root; } } //将val节点插入到parent上 TreeNode* node = new TreeNode(val); //根据当前值和上一个节点的值的大小,来决定插入左子树,还是右子树 if(parent->val > val) { parent->left = node; } else { parent->right = node; } return root; }
98. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
参考代码
//中序遍历二叉搜索树,遍历的结果一定是从小到大的. long pre = LONG_MIN; bool isValidBST(TreeNode* root) { if(root==NULL){ return true; } //访问左子树 if(!isValidBST(root->left)){ return false; } //访问当前节点 if(root->val<=pre){ return false; } pre = root->val;//更新pre //访问右子树 return isValidBST(root->right); }
