# LeetCode 98. Validate Binary Search Tree

## Description

Title

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.

Example 1:

``````   2
/ \
1   3
``````

Input: [2,1,3]

Output: true

Example 2:

``````    5
/ \
1   4
/ \
3   6
``````

Input: [5,1,4,null,null,3,6]

Output: false

Explanation: The root node’s value is 5 but its right child’s value is 4.

# LeetCode 97. Interleaving String

## Description

Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: `s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"`

Output: `true`

Example 2:

Input: `s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"`

Output: `false`

# LeetCode 96. Unique Binary Search Trees

## Description

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3

Output: 5

Explanation: Given n = 3, there are a total of 5 unique BST’s:

``````   1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3
``````

# LeetCode 94. Binary Tree Inorder Traversal

## Description

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

``````Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]
``````

Follow up: Recursive solution is trivial, could you do it iteratively?

# LeetCode 93. Restore IP Addresses

## Description

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

``````Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
``````

# LeetCode 92. Reverse Linked List II

## Description

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

``````Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
``````

# LeetCode 91. Decode Ways

## Description

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

``````'A' -> 1
'B' -> 2
...
'Z' -> 26
``````

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

``````Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
``````

Example 2:

``````Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
``````

# LeetCode 90. Subsets II

## Description

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

``````Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
``````

Programer

ChengDu·China
-