Binary Search Tree

Tree 的一种，比较特殊。

技巧

1。左子树的值 < 当前节点 < 右子树的值。

2。中序遍历（Inorder Traversal）会返回递增序列。

3。做DFS的时候，一般需要给定 min 和 max ，即当前节点的取值范围。

e.g. Unique Binary Search Trees II

经典题目

285 Inorder Successor in BST

def inorderSuccessor(self, root, p):
    """
    :type root: TreeNode
    :type p: TreeNode
    :rtype: TreeNode
    """
    if p.right is not None:
        return self.leftmost(p.right)
    else:
        return self.firstLarger(root, p)

def firstLarger(self, root, p):
    ans = None
    while root is not None:
        if root.val > p.val:
            ans = root
            root = root.left
        else:
            root = root.right
    return ans

def leftmost(self, node):
    while node.left is not None:
        node = node.left
    return node

95 Unique Binary Search Trees II

public List<TreeNode> generateTrees(int n) {
    if (n == 0) return new ArrayList<>();
    return helper(1, n);
}

private List<TreeNode> helper(int min, int max) {
    if (min > max) {
        TreeNode node = null;
        return Arrays.asList(node);
    }
    List<TreeNode> ans = new ArrayList<>();
    for (int i = min; i <= max; i++) {
        List<TreeNode> left = helper(min, i - 1);
        List<TreeNode> right = helper(i + 1, max);
        for (TreeNode l : left) {
            for (TreeNode r : right) {
                TreeNode node = new TreeNode(i);
                node.left = l;
                node.right = r;
                ans.add(node);
            }
        }
    }
    return ans;
}

BST Sequences (CC189)

/*
	A binary search tree was created by traversing through an array 
	from left to right and inserting each element. 
	Given a binary search tree with distinct elements, 
	print all possible arrays that could have led to this tree.
*/

public List<List<Integer>> solution(TreeNode root) {
	List<List<Integer>> rs = new ArrayList<List<Integer>>();
	if(root == null) {
		rs.add(new ArrayList<Integer>());
		return rs;
	}

	List<Integer> prefix = new ArrayList<>();
	prefix.add(root.val);

	List<List<Integer>> leftSeq = solution(root.left);
	List<List<Integer>> rightSeq = solution(root.right);

	for(List<Integer> left : leftSeq) {
		for(List<Integer> right : rightSeq) {
			List<List<Integer>> weaved = new ArrayList<List<Integer>>();
			weaveLists(left, right, weaved, prefix);
			rs.addAll(weaved);
		}
	}
	return rs;
}

private void weaveLists(List<Integer> left, List<Integer> right, List<List<Integer>> results, List<Integer> prefix) {
	if(left.isEmpty() || right.isEmpty()) {
		List<Integer> rs = new ArrayList<Integer>(prefix);
		rs.addAll(left);
		rs.addAll(right);
		results.add(rs);
		return;
	}

	int headLeft = left.remove(0);
	prefix.add(headLeft);
	weaveLists(left, right, results, prefix);
	prefix.remove(prefix.size() - 1);
	left.add(0, headLeft);

	int headRight = right.remove(0);
	prefix.add(headRight);
	weaveLists(left, right, results, prefix);
	prefix.remove(prefix.size() - 1);
	right.add(0, headRight);
}

Rank from Stream (CC189)

Imagine you are reading in a stream of integers. Periodically, you wish to be able to loop up the rank of a number x (the number of values less than or equal to x). Implement the data structures and algorithms to support these operations. That is, implement the method track(int x), which is called when each number is generated, and the method getRankOfNumber(int x), which returns the number of values less than or equal to x (not including x itself).

// EXAMPLE
// Stream (in order of appearance): 5, 1, 4, 4, 5, 9, 7, 13, 3
// getRankOfNumber(1) = 0
// getRankOfNumber(3) = 1
// getRankOfNumber(4) = 3

// We gonna build a binary search tree, with each node storing additional data.

class RankNode {
	private int leftSize = 0;
	private RankNode left, right;
	private int val = 0;

	public RankNode(int num) {
		this.val = num;
	}

	public void insert(int num) {
		if(num <= val) {
			if(left != null) {
				left.insert(num);
			} else {
				left = new RankNode(num);
			}
			leftSize++;
		} else {
			if(right != null) {
				right.insert(num);
			} else {
				right = new RankNode(num);
			}
		}
	}

	public int getRank(int num) {
		if(num == val) {
			return leftSize;
		} else if (num < val) {
			if(left == null) {
				return -1;
			} else {
				return left.getRank(num);
			}
		} else {
			if (right == null) {
				return -1;
			} else {
				return leftSize + 1 + right.getRank(num);
			}
		}
	}
}

RankNode root = null;

void track(int number) {
	if(root == null) {
		root = new RankNode(number);
	} else {
		root.insert(number);
	}
}

// track() : O(log N), for balanced BST
// getRank() : O(log N), for balanced BST