leetcode
九章

题目描述

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
九章

题目描述

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 isD, 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:

![](https://assets.leetcode.com/uploads/2019/04/08/recover-a-tree-from-
preorder-traversal.png)

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

Example 2:

![](https://assets.leetcode.com/uploads/2019/04/11/screen-
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:

![](https://assets.leetcode.com/uploads/2019/04/11/screen-
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
九章

题目描述

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
九章

题目描述

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

答案

思路：

任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。

心得：

在递归函数的开头判断是否为 None，而不用分别判断 左 右和 root



难度：Easy

leetcode
九章

题目描述

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.

Tags: Tree, Breadth-first Search

Difficulty: Easy

答案

难度：Easy

leetcode
九章

题目描述

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

答案

难度：Easy

leetcode
九章

题目描述

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

答案

难度：Easy

leetcode
九章

题目描述

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

答案

难度：Easy

leetcode
九章

题目描述

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

答案

难度：Easy

leetcode
九章

题目描述

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

答案