算法与数据结构基础 - 二叉查找树(Binary Search Tree)
二叉查找树基础
二叉查找树(BST)满足这样的性质,或是一颗空树;或左子树节点值小于根节点值、右子树节点值大于根节点值,左右子树也分别满足这个性质。
利用这个性质,可以迭代(iterative)或递归(recursive)地用O(lgN)的时间复杂度在二叉查找树中进行值查找。
相关LeetCode题:
700. Search in a Binary Search Tree 题解
701. Insert into a Binary Search Tree 题解
二叉查找树与有序序列
由性质可知,如果按中序(inorder)遍历二叉查找树,我们将得到递增序列;反过来,如果中序遍历的结果不是递增序列,则所遍历树不是二叉查找树。以下框架适用于多数需要中序遍历二叉树的场景:
//98. Validate Binary Search Tree
bool isValidBST(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* prv=NULL;
while(root!=NULL||!st.empty()){
while(root!=NULL){
st.push(root);
root=root->left;
}
root=st.top();
st.pop();
if(prv!=NULL&&prv->val>=root->val) return false;
prv=root;
root=root->right;
}
return true;
}
二叉查找树可以生成有序序列,同样可以用有序序列构造二叉查找树:递归地以中间值为root,左侧为左子树、右侧为右子树。
相关LeetCode题:
98. Validate Binary Search Tree 题解
173. Binary Search Tree Iterator 题解
230. Kth Smallest Element in a BST 题解
108. Convert Sorted Array to Binary Search Tree 题解
449. Serialize and Deserialize BST 题解
二叉查找树前序遍历
若对二叉查找树进行前序遍历(preorder),也将得到满足一定规则的序列 [根节点val, 左子树, 右子树],两者也可以相互构造。
相关LeetCode题:
255. Verify Preorder Sequence in Binary Search Tree 题解
1008. Construct Binary Search Tree from Preorder Traversal 题解
最新文章
- $(function(){}) 与(function(){})()在执行时的优先级
- 最近遇到的jsfl开发问题总结
- JAVA volatile 关键字
- [selector1][selector2][selectorN]
- CSS中的浮动问题
- xss攻击入门
- 45种Javascript技巧大全【转藏】
- js 多媒体audio video
- LINUX服务器上新增用户名
- Part 3:视图和模板--Django从入门到精通系列教程
- AltiumDesigner印制导线的走向及形状
- Django Rest framework 之 解析器
- Java之枚举举例
- C++学习(十四)(C语言部分)之 数组
- WPF GridLinesVisibility属性
- python中安装Tensorflow
- solr 通过【配置、多值字段、动态字段】来解决文本表达式查询精确到句子的问题
- 【AtCoder】AGC005F - Many Easy Problems
- Android几种layout(布局)的区别
- 第90天:HTML5中文件API和拖放操作
热门文章
- django执行mysql恢复的时候出现“The request&#39;s session was deleted before the request completed. The user may have logged out in a concurrent request, for example.”
- c++稍微复杂桶排序(未完待续~)
- Java连载5-标识符、关键字和字面值
- c++学习书籍推荐《C++ Primer Plus中文版(第6版)》下载
- 基于lua-nginx-module(openresty)的WEB应用防火墙
- python数据库查询转dataframe
- 剑指offer第二版-总结:二叉树的遍历
- 程序员要搞明白CDN,这篇应该够了
- 开设“C程序答疑解惑”的初衷
- 求1-2/3+3/5-4/7+......49/97和(C语言实现)