# leetcode Tree 整理版

• 依照leetcode定义 自己写的createTree方法，便于测试中序遍历的下标和
• 94 Binary Tree Inorder Traversal
• 95 Unique Binary Search Trees II
• 96 Unique Binary Search Trees
• 98 Validate Binary Search Tree
• 99 Recover Binary Search Tree
• 100 Same Tree
• 101 Symmetric Tree
• 102 Binary Tree Level Order Traversal
• 103 Binary Tree Zigzag Level Order Traversal
• 104 Maximum Depth of Binary Tree
• 105 Construct Binary Tree from Preorder and Inorder Traversal
• 106 Construct Binary Tree from Inorder and Postorder Traversal
• 107 Binary Tree Level Order Traversal II
• 108 Convert Sorted Array to Binary Search Tree
• 109 Convert Sorted List to Binary Search Tree
• 110 Balanced Binary Tree
• 111 Minimum Depth of Binary Tree
• 112 Path Sum
• 113 Path Sum II
• 114 Flatten Binary Tree to Linked List
• 116 Populating Next Right Pointers in Each Node
• 117 Populating Next Right Pointers in Each Node II
• 124 Binary Tree Maximum Path Sum
• 129 Sum Root to Leaf Numbers
• 144 Binary Tree Preorder Traversal
• 145 Binary Tree Postorder Traversal
• 173 Binary Search Tree Iterator
• 199 Binary Tree Right Side View
• 222 Count Complete Tree Nodes
• 226 Invert Binary Tree
• 230 Kth Smallest Element in a BST
• 235 Lowest Common Ancestor of a Binary Search Tree
• 236 Lowest Common Ancestor of a Binary Tree
• 257 Binary Tree Paths
• 297 Serialize and Deserialize Binary Tree
• 449. Serialize and Deserialize BST

## 1.首先是leetcode对于树的表示方法：

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

The above binary tree is serialized as "{1,2,3,null,null,4,null,null,5}".

## 2.题解归类

• 用前序和中序建树105
• 用后序和中序建树106
• 数组构建BST 108
• 链表构建BST 109

### 2.树的遍历

• 前序 144
• 中序 94
• 后序 145
• 层次 102 103 107

• 求深度 104
• 是否平衡是平衡树 110
• 最小深度 111

### 4.BST树

• 判断BST是否合法 98
• 恢复BST 99
• BST实现迭代：173（用到某一遍历）

## 3.题解代码（按题号顺序）

### 94. Binary Tree Inorder Traversal

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

For example: Given binary tree {1,#,2,3},

return [1,3,2].

Python

Python非递归版本

### 95. Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1..._n_.

For example, Given n = 3, your program should return all 5 unique BST's shown below.

C++

Python

### 96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1..._n_?

For example, Given n = 3, there are a total of 5 unique BST's.

C++

Python

### 98. Validate Binary Search Tree

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.

• 根结点大于左子树结点， 根结点小于右子树结点。
• 左右子树是合法的BST

1. 递归判断左右子树。需要用出现过的最大、最小值来判断。 如左子树最大值不可能超过根，右子树最小值不可能小于根
2. 中序遍历。 合法的BST中序遍历必为有序序列。

C++

Python

C++

Python

### 99. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

C++

Python

### 100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

C++

Python

### 101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

But the following is not:

Note: Bonus points if you could solve it both recursively and iteratively.

C++

Python

### 102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree {3,9,20,#,#,15,7},

return its level order traversal as:

C++

Python

### 103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree {3,9,20,#,#,15,7},

return its zigzag level order traversal as:

C++

Python

### 104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

C++

Python

### 105 . Construct Binary Tree from Preorder and Inorder Traversal

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

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

• 左子树，每次递归的下标为：[pb + 1, pb + len + 1)   [ ib, ib+len)
• 右子树：[pb + len + 1, pe)  [ib + len + 1, ie)

Python

C++

### 106. Construct Binary Tree from Inorder and Postorder Traversal

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

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

• 左子树，每次递归的下标为：[pb,  pb + len)   [ ib, ib+len)
• 右子树：[pb + len, pe - 1)  [ib + len + 1, ie)

Python

C++

### 107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example: Given binary tree {3,9,20,#,#,15,7},

return its bottom-up level order traversal as:

C++

Python

### 108. Convert Sorted Array to Binary Search Tree

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

C++

Java

Python

### 109 Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

• 使用快慢指针
• 复杂度O(nlogn)

C++

Java

Python

BST利用中序遍历为有序的性质，来建树。

• 相当于链表保存的为中序遍历
• 要让建出来的树尽可能的平衡，那么用二分，mid = (L + R)/2，左边的就是[L,mid-1]，右边[mid+1,R]

C++

Java

Python

### 110. Balanced Binary Tree

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.

C++

Python

### 111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

C++

Python

### 112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example: Given the below binary tree and sum = 22,

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

C++

Python

### 113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example: Given the below binary tree and sum = 22,

return

C++

Python

### 114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, Given

The flattened tree should look like:

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

C++

Python

### 116.  117 Populating Next Right Pointers in Each Node

Given a binary tree

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example, Given the following perfect binary tree,

After calling your function, the tree should look like:

C++

Python

C++

Python

### 124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example: Given the below binary tree,

Return 6.

• L+R+root.val (左右子树和根构成路径为最大值，就是题目的情况）
• max(L,R) + root.val(左或者右子树和根构成最大值）
• root.val本身为最大值

• max(L,R) + root.val 某一条路径
• root.val  只是该结点（下面都是负的了）

Python

### 129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Python

C++

### 144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example: Given binary tree {1,#,2,3},

return [1,2,3].

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

1. 直接递归。没难度。
2. 用栈，记得应先右子树入栈。（why?递归的时候是先左子树的，而栈后进先出，故左子树要放后面入栈）

C++

Python

C++

Python

### 145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example: Given binary tree {1,#,2,3},

return [3,2,1].

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

C++

Python

### 173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

leetcode 173 Binary Search Tree Iterator

Python

### 199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example: Given the following binary tree,

You should return [1, 3, 4].

• BFS，直接求得每一层最右边的，很好理解，我就不想写了。
• DFS：先求深度，然后dfs，每次将找到的放在相应的层上。由于右面放的一定是右边的结点，所以能保证正确。

### 222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.

C

Python

### 226. Invert Binary Tree

Invert a binary tree.

to

C++

### 230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

### 235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

LCA问题可以见我博客 二叉树最近公共祖先详解（LCA问题详解）

### 236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

LCA问题可以见我博客 二叉树最近公共祖先详解（LCA问题详解）

Python

### 257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

All root-to-leaf paths are:

### 297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

BFS：

• 对于序列化，只需要首先将根放入队列，然后每次从队列取第一个cur。如果cur为空，输出"null,"，否则输出cur->val + ","。这里我用都好分隔符
• 对于反序列化，按分隔符","分割，每次取出。如果当前字符串t不为"null",则创建一个值为t的TreeNode，把当前结点的left或者right指向它。详见代码。

C++

Java

Python

Java

### 449. Serialize and Deserialize BST

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

BST和其他的有啥用呢？在297题中，我们用null表示节点为空。但是这题不需要。我们可以根据节点的大小来判断应该在左子树还是右子树。

C++

Java

Python

• 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！