# leetcode 95. Unique Binary Search Trees II

## 题目描述

Given an integer n , generate all structurally unique BST ‘s (binary
search trees) that store values 1 … n.

Example:

``````Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

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

Tags: Dynamic Programming, Tree

Difficulty: Medium



# leetcode 1028. Recover a Tree From Preorder Traversal

## 题目描述

We run a preorder depth first search on the `root` of a binary tree.

At each node in this traversal, we output `D` dashes (where `D` is the depth
of this node), then we output the value of this node. (If the depth of a
node is`D`, the depth of its immediate child is `D+1`. The depth of the root
node is `0`.)

If a node has only one child, that child is guaranteed to be the left child.

Given the output `S` of this traversal, recover the tree and return its
`root`.

Example 1:

preorder-traversal.png)

``````Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]``````

Example 2:

shot-2019-04-10-at-114101-pm.png)

``````Input: "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]``````

Example 3:

shot-2019-04-10-at-114955-pm.png)

``````Input: "1-401--349---90--88"
Output: [1,401,null,349,88,90]``````

Note:

• The number of nodes in the original tree is between `1` and `1000`.
• Each node will have a value between `1` and `10^9`.

Tags: Tree, Depth-first Search

Difficulty: Hard



# leetcode 572. Subtree of Another Tree

## 题目描述

Given two non-empty binary trees s and t , check whether tree t
has exactly the same structure and node values with a subtree of s. A
subtree of s is a tree consists of a node in s and all of this node’s
descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

``````    3
/ \
4   5
/ \
1   2``````

Given tree t:

``````  4
/ \
1   2``````

Return true , because t has the same structure and node values with a
subtree of s.

Example 2:
Given tree s:

``````    3
/ \
4   5
/ \
1   2
/
0``````

Given tree t:

``````  4
/ \
1   2``````

Return false.

Tags: Tree

Difficulty: Easy



# leetcode 543. Diameter of Binary Tree

## 题目描述

Given a binary tree, you need to compute the length of the diameter of the
tree. The diameter of a binary tree is the length of the longest path
between any two nodes in a tree. This path may or may not pass through the
root.

Example:
Given a binary tree

``````    1
/ \
2   3
/ \
4   5    ``````

Return 3 , which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of
edges between them.

Tags: Tree

Difficulty: Easy



# leetcode 993. Cousins in Binary Tree

## 题目描述

In a binary tree, the root node is at depth `0`, and children of each depth
`k` node are at depth `k+1`.

Two nodes of a binary tree are cousins if they have the same depth, but have
different parents.

We are given the `root` of a binary tree with unique values, and the values
`x` and `y` of two different nodes in the tree.

Return `true` if and only if the nodes corresponding to the values `x` and `y`
are cousins.

Example 1:

``````Input: root = [1,2,3,4], x = 4, y = 3
Output: false``````

Example 2:

``````Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true``````

Example 3:

``````Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false``````

Note:

1. The number of nodes in the tree will be between `2` and `100`.
2. Each node has a unique integer value from `1` to `100`.

Difficulty: Easy

# leetcode 538. Convert BST to Greater Tree

## 题目描述

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every
key of the original BST is changed to the original key plus sum of all keys
greater than the original key in BST.

Example:

``````Input: The root of a Binary Search Tree like this:
5
/   \
2     13

Output: The root of a Greater Tree like this:
18
/   \
20     13``````

Tags: Tree

Difficulty: Easy

# leetcode 653. Two Sum IV - Input is a BST

## 题目描述

Given a Binary Search Tree and a target number, return true if there exist two
elements in the BST such that their sum is equal to the given target.

Example 1:

``````Input:
5
/ \
3   6
/ \   \
2   4   7

Target = 9

Output: True``````

Example 2:

``````Input:
5
/ \
3   6
/ \   \
2   4   7

Target = 28

Output: False``````

Tags: Tree

Difficulty: Easy

# leetcode 637. Average of Levels in Binary Tree

## 题目描述

Given a non-empty binary tree, return the average value of the nodes on each
level in the form of an array.

Example 1:

``````Input:
3
/ \
9  20
/  \
15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].``````

Note:

1. The range of node’s value is in the range of 32-bit signed integer.

Tags: Tree

Difficulty: Easy

# leetcode 872. Leaf-Similar Trees

## 题目描述

Consider all the leaves of a binary tree. From left to right order, the
values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is ```(6, 7, 4, 9, 8)```.

Two binary trees are considered leaf-similar if their leaf value sequence
is the same.

Return `true` if and only if the two given trees with head nodes `root1` and
`root2` are leaf-similar.

Note:

• Both of the given trees will have between `1` and `100` nodes.

Tags: Tree, Depth-first Search

Difficulty: Easy

# leetcode 965. Univalued Binary Tree

## 题目描述

A binary tree is univalued if every node in the tree has the same value.

Return `true` if and only if the given tree is univalued.

Example 1:

``````Input: [1,1,1,1,1,null,1]
Output: true``````

Example 2:

``````Input: [2,2,2,5,2]
Output: false``````

Note:

1. The number of nodes in the given tree will be in the range `[1, 100]`.
2. Each node’s value will be an integer in the range `[0, 99]`.

Tags: Tree

Difficulty: Easy

:D 一言句子获取中...