Review
-
有数值
-
有序树：lch< root< rch
递归和迭代遍历不同于普通二叉树
搜索BST
700.二叉搜索树中的搜索
-
有：返回以存储val节点为根的子树
-
无：NULL
AC1：递归
-
参数和返回值：
-
根节点 & 待寻值
-
节点
-
-
终止条件：根为空||匹配到val
-
单层逻辑：
-
有序树：从左到右搜索
-
返回值为节点类型，记得定义一个变量存储节点
-
#include<iostream>
#include"TreeNode.h"
using namespace std;
TreeNode* BST(TreeNode* root,int val){
if(root==nullptr || root->val==val)
return root;
TreeNode* result;
if(root->val>val)
result=BST(root->left,val);
if(root->val<val)
result=BST(root->right,val);
return result;
}
int main(){
//建树
return 0;
}
AC2：迭代
-
对于迭代，通常：
-
用stack栈模拟DFS深度遍历
-
用queue队列模拟BFS广度遍历
-
-
但对于BST，由于其有序，可以不用DS辅助
TreeNode* InteratinBST(TreeNode* root,int val){
while(root!=nullptr){
if(root->val>val)
root=root->left;
else if(root->val<val)
root=root->right;
else return root;
}
return nullptr;
}
插入BST
[701. 二叉搜索树中的插入操作](https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/)
-
将值放入树，返回BST的根节点
-
存在多种有效的插入方式
-
不用调整二叉树的结构
-
只需要遍历树，找到空节点并插入即可
递归：
-
参数及返回值：
-
TreeNode*
-
返回根节点--每一次递归返回都要用上一层的节点接住
-
root , val（插入值)
-
-
终止条件：找到合适的空节点并插入数值
-
单层逻辑：搜索数值
AC：
#include<iostream>
#include"TreeNode.h"
using namespace std;
TreeNode* insertIntoBST(TreeNode* root,int val){
if(root==nullptr){
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;
}
int main(){
return 0;
}
删除BST中的节点
450.删除二叉搜索树中的节点
- 要考虑多种情况，比插入节点复杂
< auto >
- 根据初始化表达式自动判断变量类型
递归：
。返回值，参数: TreeNode* ; root , key
。终止条件: nullptr--找不到删除的节点
。单层逻辑:
-
没找到删除的节点，遇空即返
-
叶子节点，直接删，返回nullptr
-
节点无左孩子，删了补右孩子
-
节点无右孩子，删了补左孩子
-
节点有俩孩子，删了补右孩子，左孩子放到右孩子最左节点做左孩子
补孩子：
-
暂存一个节点放child
-
删root
-
返回retNode（暂存节点）给上一层
AC：
#include<iostream>
#include"TreeNode.h"
using namespace std;
TreeNode* deleteNode(TreeNode* root,int key){
//1.
if(root==nullptr)
return root;
if(root->val==key){
//2.
if(root->left==nullptr && root->right==nullptr){
delete root;
return nullptr;
}
//3.
if(root->left==nullptr){
auto retNode=root->right;
delete root;
return retNode;
}
//4.
if(root->right==nullptr){
auto retNode=root->left;
delete root;
return retNode;
}
//5.
else{
TreeNode* cur=root->right;
TreeNode* tmp=root;
while(cur->left){//cur->left!=nullptr
cur=cur->left;
}
cur->left=root->left;
root=root->right;
delete tmp;
return root;
}
}
if(root->val>key) root->left=deleteNode(root->left,key);
if(root->val<key) root->right=deleteNode(root->right,key);
return root;
}
验证BST
98.验证二叉搜索树
- 将树转为数组
AC：