Binary Search Tree Iterator

Description

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
NOTE: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Solution

In a binary search tree, in-order traversal retrieves data in sorted order. In general we traverse the tree from left to right, thus we’ll get a sequence in ascending order. With this knowledge in mind, we can easily implement an iterator over a BST.

In-order traversal review

iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right

We cannot directly apply above iterative in-order traversal to the solution, because we are required to use O(h) memory. We can easily overcome this by dividing the total process into two stages. In first stage, we put elements into a stack, the number of elements is O(h). In second stage, we retrieve element.

C++ implementation

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
private:
    stack<TreeNode*> st;

public:
    BSTIterator(TreeNode *root) {
        auto p = root;
        while (root) {
            st.push(root);
            root = root->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !st.empty();
    }

    /** @return the next smallest number */
    int next() {
        auto n = st.top();
        st.pop();
        auto p = n->right;
        while (p) {
            st.push(p);
            p = p->left;
        }
        return n->val;
    }
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

In our constructor of BSTIterator, we continue to push element of left node into the stack until left node is null. After this, there are O(h) elements in the stack. hasNext() just checks if the stack is empty, which is O(1). In next(), we remove an element from the stack and deal with its right subtree until we push the next smallest element into the stack, the push operations don’t matter, the number of elements in stack remains O(h). (Todo: time complexity analysis)

Advertisements

Italics 和 true-color支持

iTerm 配置

创建文件 xterm-256color-italic.terminfo

xterm-256color-italic|xterm with 256 colors and italic,
  sitm=\E[3m, ritm=\E[23m,
  use=xterm-256color,

安装:

tic -x xterm-256color-italic.terminfo

针对某个profile,设置文本渲染选项,确保Italic text allowed勾选,将term的type设置为xterm-256color-italic

Vim 配置

~/.vimrc中添加如下配置项:

if (has("termguicolors"))
  set termguicolors
endif
let g:material_theme_style = 'default'
let g:material_terminal_italics = 1
set background=dark
colorscheme material

以上配置选择了一款支持italics的主题material color theme,也可以选择其他支持italics的主题。

问题

当使用ssh登录到远端服务器时,远端服务器的term type被设置为xterm-256color-italic,但其实并不存在,需要重新设置为xterm-256color。同时,ls的表现也异常,无色彩输出。

以上问题可通过在服务器终端的配置文件(~/.bashrc)中添加下述配置项解决:

export TERM=xterm-256color
alias ls='ls --color=auto'

效果

True-colors-italics-vim-iTerm

外面的世界

知道的越多,越觉得需要了解更多。在有墙的环境下生活久了,会产生一种错觉,觉得墙所限的区域就是全世界,待得越久这种错觉就越真实。殊不知墙外还有世界,它或许缤纷多彩。以下介绍一种越墙方法。

购买一台VPS

推荐去virmach购买,价格良心。

在VPS上搭建Shadowsocks(ss)

搭建步骤如下:

apt-get update
apt-install python-pip
pip install shadowsocks

启动ssserver:

ssserver -c /etc/shadowsocks.json -d start

其中/etc/shadowsocks.json的内容如下:

{
    "server": "server_ip",
    "server_port": server_port,
    "local_address": "127.0.0.1",
    "local_port": 1080,
    "password": "password",
    "timeout": 300,
    "method": "aes-256-cfb",
    "fast_open": false
}

ss client

下载对应平台的Shadowsocks,添加server配置。你也可以搭配SwitchyOmega使用。Enjoy yourself!