Delete Node in a BST
BST中删除节点, 经典算法: 先BST搜到节点, 然后: 1. 如果左子树是空, 返回右子树. 2. 如果右子树是空, 返回左子树. 3. 两个都不是空的, 找到右子树最左的节点, 赋值给root, 然后继续删除右子树root的当前值.
BST
Two Sum IV – Input is a BST
给一个BST, 返回true 如果其中两个node的val和等于k. 直接遍历树, 然后用set记录一下差值. 这个题我没用到bst的性质, 不知道为什么
Minimum Distance Between BST Nodes
找BST上两个node之间的最小值, 因为是bst所以已经是sorted了, 直接比较就可以
Increasing Order Search Tree
把一个BST树改写成链表. 这个我用的是dummy node的思路, 建个dummy node然后一点点依照题目构建答案.
Find kth smallest element in BST 找第k个小(大)的值在BST中
今天geeksforgeeks上刷出来的题.一看不能用stack, 基本就是Morris遍历了. 但是做了一下, 发现需要注意的地方挺多的, 比如当我们算visit的时候, 在rebuild link后, 我们也需要increase counter. 不然打印出来的是The Bottom of Tree 代码: public static int find(TreeNode root, int k) { int count = 0;// int res = Integer.MAX_VALUE; TreeNode cur = root; while (cur != null) { if (cur.left == null) { // if left == null, then we print(or do something, in […]
[Google] Serialization and Deserialization BST 二叉树编码和解码
这是一道Google的面试题. 当我第一次看到这题的时候, 第一个感觉, 树, 编码,解码, 那不就是Prufer Code么. 拿起笔就开始写, 后来感觉电面不应该这么复杂, 而且Prufer code对象是Labeled Tree, 这里并没有使用到BST的特殊性质. 于是赶紧回想刷过的题, 突然想起Leetcode上面的编码方式: 这个编码的特点是: Inorder Traversal. Null = # Code容易写. 所以编码的code是: public static String serialize (TreeNode root) { StringBuilder sb = new StringBuilder(); if (root == null) sb.append(“#”); else { sb.append(root.val); sb.append(serialize(root.left)); sb.append(serialize(root.right)); } return sb.toString(); } 解码的特点是: 因为已知编码是Inorder, 所以解码也是Inorder 要注意如果解码到#, 需要return null. […]