Validate Binary Search Tree

Problem

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

---

Idea

这个题一定要注意，判断bst并不是只检查以下当前节点和其左右子树是否正确。 应该确保每个节点都不大于当前子树的最大值和最小值。举个例子

---

Solution

---

Roman to Integer

Problem

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

---

Idea

一定要注意好radix和symbol两个数组的顺序，依次遍历s，把找到的子串删掉，然后继续，并更新result.

---

Solution

---

Construct Binary Tree from Inorder and Postorder Traversal

Problem

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

---

Idea

和之前那个inorder和preorder建树的思路一样，在preorder里找根，在inorder里找左子树右子树.

---

Solution

---

Balanced Binary Tree

Problem

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

---

Idea

深度优先遍历，得到每个点的左子树和右子树高度，然后比较。

---

Solution

---

Construct Binary Tree from Preorder and Inorder Traversal

Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

---

Idea

Preorder那个数组找到根，inorder那个数组找到根的位置，然后左边为左子树，右边为右子树。

---

Solution

---

Convert Sorted Array to Binary Search Tree

Problem

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

---

Idea

就是二分法.找到num的中间元素, 然后二分去build左子树与右子树

---

Solution

---

Combination Sum

Problem

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,

A solution set is:
[7]
[2, 2, 3]

---

Idea

本质上是DFS，查找所有可行解的范围

To search for all combination, we use a backtracking algorithm. Here, we use the above example of candidate={2,3,6,7} and target=7.

First, we start with a sum of 0. Then, we iterate over all possibilities that can be added to sum, which yields the possible set of sum={2,3,6,7}. Assume now that sum=2, we continue adding all possible candidate numbers {2,3,6,7} to sum=2, which yields sum={4,5,8,9}. Each step we have to use an array to keep track of all the indices of candidate numbers that add to the current sum, so that we can print the combination later. The next case would be sum=3. We look at all possible candidate numbers {3,6,7} to be added to sum=3, which yields sum={6,9,10}. Note that there is no need to look backward (ie, candidate numbers that are smaller than 3), as this would only yield duplicate results. We keep doing this recursively, until we reach the conditions below, where we stop.

---

Solution

---