Menu Sidebar
Menu

BST

Delete Node in a BST

BST中删除节点, 经典算法: 先BST搜到节点, 然后: 1. 如果左子树是空, 返回右子树. 2. 如果右子树是空, 返回左子树. 3. 两个都不是空的, 找到右子树最左的节点, 赋值给root, 然后继续删除右子树root的当前值.

Find kth smallest element in BST 找第k个小(大)的值在BST中

今天geeksforgeeks上刷出来的题.一看不能用stack, 基本就是Morris遍历了. 但是做了一下, 发现需要注意的地方挺多的, 比如当我们算visit的时候, 在rebuild link后, 我们也需要increase counter. 不然打印出来的是The Bottom of Tree 代码:

 

[Google] Serialization and Deserialization BST 二叉树编码和解码

这是一道Google的面试题. 当我第一次看到这题的时候, 第一个感觉, 树, 编码,解码, 那不就是Prufer Code么. 拿起笔就开始写, 后来感觉电面不应该这么复杂, 而且Prufer code对象是Labeled Tree, 这里并没有使用到BST的特殊性质. 于是赶紧回想刷过的题, 突然想起Leetcode上面的编码方式: 这个编码的特点是: Inorder Traversal. Null = # Code容易写. 所以编码的code是:

解码的特点是: 因为已知编码是Inorder, 所以解码也是Inorder 要注意如果解码到#, 需要return null. 所以解码的code是:

 

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

November 2019
M T W T F S S
« Oct    
 123
45678910
11121314151617
18192021222324
252627282930