578.最近公共祖先III
描述
给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先 LCA。两个节点的最近公共祖先，是指两个节点的所有父亲节点中(包括这两个节点)，离这两个节点最近的公共的节点。返回 null 如果两个节点在这棵树上不存在最近公共祖先的话。
注意事项
这两个节点未必都在这棵树上出现。
样例
给出下面这棵树：
4/ \3 7/ \5 6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
LCA(5, 8) = null
PS
A 和 B 不一定在树中存在，需要定义纪录存在与否的变量，如果不存在，无需去寻找公共祖先
// An highlighted block
var foo = 'bar';
2019/9/5
# #法二
# #2019/9/5
# class TreeNode:
# def __init__(self,val):
# self.val=val
# self.left,self.right = None,None
#
# class Solution:
# def lowestCommonAncestor(self,root,A,B):
# # A&B=>LCA
# # !A&!B=>None
# # A&!B=>A
# # B&!A=>B
# if (root is None or root == A or root == B):
# return root # 若root为空或者root为A或者root为B，说明找到了A和B其中一个
# left = self.lowestCommonAncestor(root.left, A, B)
# right = self.lowestCommonAncestor(root.right, A, B)
# if (left is not None and right is not None):
# return root # 若左子树找到了A，右子树找到了B，说明此时的root就是公共祖先
# if (left is None): # 若左子树是none右子树不是，说明右子树找到了A或B
# return right
# if (right is None): # 同理
# return left
# return None
#
# a = Tree = TreeNode(2)
# b = Tree.left = TreeNode(1)
# c = Tree.right = TreeNode(3)
# d = b.left = TreeNode(4)
# s = Solution()
# print(s.lowestCommonAncestor(a, b, d).val)
#
https://blog.csdn.net/wenqiwenqi123/article/details/79952043
95. 验证二叉查找树
给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：
节点的左子树中的值要严格小于该节点的值。
节点的右子树中的值要严格大于该节点的值。
左右子树也必须是二叉查找树。
一个节点的树也是二叉查找树。
样例：
一个例子：
// An highlighted block2/ \
1 4/ \3 5
上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.
// An highlighted block
var foo = 'bar';
2019/9/5
246，二叉树的路径和||
描述
给一棵二叉树和一个目标值，设计一个算法找到二叉树上的和为该目标值的所有路径。 路径可以从任何结点出发和结束，但是需要是一条一直往下走的路线。也就是说， 路径上的结点的层级是逐个递增的。
样例
对于二叉树：
1/ \2 3/ /4 2
给定目标值6。那么满足条件的路径有两条：
[[2, 4],[1, 3, 2]]
// An highlighted block
var foo = 'bar';
给出一棵二叉树，返回其节点值的后序遍历。
Example
样例 1:
输入：{1,2,3}
输出：[2,3,1]
解释：
1/ \2 3
它将被序列化为{1,2,3}
后序遍历
样例 2:
输入：{1,#,2,3}
输出：[3,2,1]
解释：
1\2/
3
它将被序列化为{1,#,2,3}
后序遍历
Challenge
你能使用非递归实现么？
Notice
首个数据为根节点，后面接着是其左儿子和右儿子节点值，"#"表示不存在该子节点。
节点数量不超过20
// An highlighted block
var foo = 'bar';
2019/9/5
https://blog.csdn.net/luoganttcc/article/details/88791244
- 二叉树的序列化和反序列化
中文English
设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。
如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。
Example
样例 1：
输入：{3,9,20,#,#,15,7}
输出：{3,9,20,#,#,15,7}
解释：
二叉树 {3,9,20,#,#,15,7}，表示如下的树结构：
// An highlighted block
var foo = 'bar';3/ \9 20/ \15 7
它将被序列化为 {3,9,20,#,#,15,7}
样例 2：
输入：{1,2,3}
输出：{1,2,3}
解释：
二叉树 {1,2,3}，表示如下的树结构：
// An highlighted block
var foo = 'bar';1/ \2 3
它将被序列化为 {1,2,3}
我们的数据是进行 BFS 遍历得到的。当你测试结果 Wrong Answer 时，你可以作为输入调试你的代码。
你可以采用其他的方法进行序列化和反序列化。
Notice
对二进制树进行反序列化或序列化的方式没有限制，LintCode 将您的 serialize 输出作为 deserialize 的输入，它不会检查序列化的结果。
// An highlighted block
var foo = 'bar';
67，二叉树的中序遍历序列
描述
给出一棵二叉树,返回其中序遍历
样例
给出二叉树 {1,#,2,3},
// An highlighted block
var foo = 'bar';1\2/3
返回 [1,3,2].
挑战
你能使用非递归算法来实现么?
中序
左根右
// An highlighted block
var foo = 'bar';
- 二叉树的前序遍历
中文English
给出一棵二叉树，返回其节点值的前序遍历。
Example
样例 1:
输入：{1,2,3}
输出：[1,2,3]
解释：
// An highlighted block
var foo = 'bar';1/ \2 3
它将被序列化为{1,2,3}
前序遍历
样例 2:
输入：{1,#,2,3}
输出：[1,2,3]
解释：
// An highlighted block
var foo = 'bar';
1\2/
3
它将被序列化为{1,#,2,3}
前序遍历
Challenge
你能使用非递归实现么？
Notice
首个数据为根节点，后面接着是其左儿子和右儿子节点值，"#"表示不存在该子节点。
节点数量不超过20
// An highlighted block
var foo = 'bar';
2019/9/5
- 二叉树最长连续序列
中文English
给一棵二叉树，找到最长连续路径的长度。
这条路径是指 任何的节点序列中的起始节点到树中的任一节点都必须遵循 父-子 联系。最长的连续路径必须是从父亲节点到孩子节点（不能逆序）。
Example
样例1:
输入:
{1,#,3,2,4,#,#,#,5}
输出:3
说明:
这棵树如图所示
1\3/ \2 4\5
最长连续序列是3-4-5，所以返回3.
样例2:
输入:
{2,#,3,2,#,1,#}
输出:2
说明:
这棵树如图所示：
2\3/ 2 / 1
最长连续序列是2-3，而不是3-2-1，所以返回2.
- 二叉树的最长连续子序列 II
中文English
给定一棵二叉树，找到最长连续序列(单调且相邻节点值相差为1)路径的长度(节点数)。
路径起点跟终点可以为二叉树的任意节点。
Example
例1:
输入:
{1,2,0,3}
输出:
4
解释:
1/ \2 0/
3
0-1-2-3
例2:
输入:
{3,2,2}
输出:
2
解释:
3/ \2 22-3619—二叉树的最长连续子序列3
描述
这题是 二叉树的最长连续子序列II 的后续。
给出一棵 k叉树，找到最长连续序列路径的长度.
路径的开头跟结尾可以是树的任意节点。
样例
一个样例如下：k叉树 5<6<7<>,5<>,8<>>,4<3<>,5<>,3<>>>，表示如下结构:
5/ \6 4/|\ /|\
7 5 8 3 5 3
返回 5, // 3-4-5-6
597—具有最大平均数的子树
描述
给一棵二叉树，找到有最大平均值的子树。返回子树的根结点。
注意事项
LintCode会打印出根结点为你返回节点的子树，保证有最大平均数子树只有一棵
样例
给一个二叉树：
1/ \-5 11/ \ / \
1 2 4 -2
返回节点 11。
596_最小子树和
描述
给一棵二叉树, 找到和为最小的子树, 返回其根节点。
注意事项
LintCode会打印根节点为你返回节点的子树。保证只有一棵和最小的子树并且给出的二叉树不是一棵空树。
样例
给一棵二叉树：
1/ \-5 2/ \ / \
0 2 -4 -5
返回节点1
- 二叉树的路径和
中文English
给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。
一个有效的路径，指的是从根节点到叶节点的路径。
Example
样例1:
输入:
{1,2,4,2,3}
5
输出: [[1, 2, 2],[1, 4]]
说明:
这棵树如下图所示：
1/ \2 4/ \2 3
对于目标总和为5，很显然1 + 2 + 2 = 1 + 4 = 5
样例2:
输入:
{1,2,4,2,3}
3
输出: []
说明:
这棵树如下图所示：
1/ \2 4/ \2 3
注意到题目要求我们寻找从根节点到叶子节点的路径。
1 + 2 + 2 = 5, 1 + 2 + 3 = 6, 1 + 4 = 5
这里没有合法的路径满足和等于3.
- 二叉树的所有路径
中文English
给一棵二叉树，找出从根节点到叶子节点的所有路径。
Example
样例 1:
输入：{1,2,3,#,5}
输出：[“1->2->5”,“1->3”]
解释：
1/ \
2 3\5
样例 2:
输入：{1,2}
输出：[“1->2”]
解释：
1/
2 - 最近公共祖先 II
中文English
给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先LCA。
两个节点的最近公共祖先，是指两个节点的所有父亲节点中（包括这两个节点），离这两个节点最近的公共的节点。
每个节点除了左右儿子指针以外，还包含一个父亲指针parent，指向自己的父亲。
Example
样例 1:
输入：{4,3,7,#,#,5,6},3,5
输出：4
解释：
4/ \3 7/ \5 6
LCA(3, 5) = 4
样例 2:
输入：{4,3,7,#,#,5,6},5,6
输出：7
解释：
4/ \3 7/ \5 6
LCA(5, 6) = 7
- 最近公共祖先
中文English
给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。
最近公共祖先是两个节点的公共的祖先节点且具有最大深度。
Example
样例 1:
输入：{1},1,1
输出：1
解释：
二叉树如下（只有一个节点）:
1
LCA(1,1) = 1
样例 2:
输入：{4,3,7,#,#,5,6},3,5
输出：4
解释：
二叉树如下:
4/ \
3 7/ \5 6
LCA(3, 5) = 4
Notice
假设给出的两个节点都在树中存在
// An highlighted block
var foo = 'bar';
class TreeNode:def __init__(self, val):self.val = valself.left, self.right = None, Noneclass Solution:"""@param: root: The root of the binary search tree.@param: A: A TreeNode in a Binary.@param: B: A TreeNode in a Binary.@return: Return the least common ancestor(LCA) of the two nodes."""def lowestCommonAncestor(self, root, A, B):# A&B=>LCA# !A&!B=>None# A&!B=>A# B&!A=>Bif (root is None or root == A or root == B):return root # 若root为空或者root为A或者root为B，说明找到了A和B其中一个left = self.lowestCommonAncestor(root.left, A, B)right = self.lowestCommonAncestor(root.right, A, B)if (left is not None and right is not None):return root # 若左子树找到了A，右子树找到了B，说明此时的root就是公共祖先if (left is None): # 若左子树是none右子树不是，说明右子树找到了A或Breturn rightif (right is None): # 同理return leftreturn Nonea = Tree = TreeNode(2)
b = Tree.left = TreeNode(1)
c = Tree.right = TreeNode(3)
d = b.left = TreeNode(4)
s = Solution()
print(s.lowestCommonAncestor(a, b, d).val)###########
// An highlighted block
var foo = 'bar';
class TreeNode:def __init__(self, val):self.val = valself.left, self.right = None, Noneclass Solution:"""@param: root: The root of the binary search tree.@param: A: A TreeNode in a Binary.@param: B: A TreeNode in a Binary.@return: Return the least common ancestor(LCA) of the two nodes.""" #def lowestCommonAncestor(self, root, A, B):if not root:return Noneif root == A or root ==B:return rootleftLCA = self.lowestCommonAncestor(root.left,A,B)rightLCA = self.lowestCommonAncestor(root.right,A,B)if not leftLCA:return rightLCAif not rightLCA:return leftLCAreturn roota = Tree = TreeNode(2)
b = Tree.left = TreeNode(1)
c = Tree.right = TreeNode(3)
d = b.left = TreeNode(4)
s = Solution()
print(s.lowestCommonAncestor(a, c, d).val)
- 平衡二叉树
中文English
给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。
Example
样例 1:
输入: tree = {1,2,3}
输出: true
样例解释:
如下，是一个平衡的二叉树。1 / \ 2 3
样例 2:
输入: tree = {3,9,20,#,#,15,7}
输出: true
样例解释:
如下，是一个平衡的二叉树。3 / \ 9 20 / \ 15 7
样例 2:
输入: tree = {1,#,2,3,4}
输出: false
样例解释:
如下，是一个不平衡的二叉树。1的左右子树高度差21 \ 2 / \ 3 4
- 二叉树的最大深度
中文English
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的距离。
Example
样例 1:
输入: tree = {}
输出: 0
样例解释: 空树的深度是0。
样例 2:
输入: tree = {1,2,3,#,#,4,5}
输出: 3
样例解释: 树表示如下，深度是3
1/ \ 2 3 / \ 4 5
它将被序列化为{1,2,3,#,#,4,5}
- 将二叉树拆成链表
中文English
将一棵二叉树按照前序遍历拆解成为一个 假链表。所谓的假链表是说，用二叉树的 right 指针，来表示链表中的 next 指针。
Example
样例 1：
输入：{1,2,5,3,4,#,6}
输出：{1,#,2,#,3,#,4,#,5,#,6}
解释：
1/ \2 5/ \ \3 4 61
\2\3\4\5\6
样例 2：
输入：{1}
输出：{1}
解释：
1
1
Challenge
不使用额外的空间耗费。
Notice
不要忘记将左儿子标记为 null，否则你可能会得到空间溢出或是时间溢出。
- 二叉树的最小深度
中文English
给定一个二叉树，找出其最小深度。
二叉树的最小深度为根节点到最近叶子节点的最短路径上的节点数量。
Example
样例 1:
输入: {}
输出: 0
样例 2:
输入: {1,#,2,3}
输出: 3
解释:
1\ 2/3 它将被序列化为 {1,#,2,3}
样例 3:
输入: {1,2,3,#,#,4,5}
输出: 2
解释:
1/ \ 2 3/ \4 5
它将被序列化为 {1,2,3,#,#,4,5}
- 将二叉树转换成双链表
中文English
将一个二叉树按照中序遍历转换成双向链表。
Example
样例 1：
输入
4/ \2 5/ \1 3 输出: 1<->2<->3<->4<->5
样例 2：输入:3/ \4 1输出:4<->3<->1
- 二叉查找树的中序后继
中文English
给定一个二叉查找树(什么是二叉查找树)，以及一个节点，求该节点在中序遍历的后继，如果没有则返回null
Example
样例 1:
输入: {1,#,2}, node with value 1
输出: 2
解释:
1\2
样例 2:
输入: {2,1,3}, node with value 1
输出: 2
解释:
2/ \1 3
二叉树的表示
Challenge
O(h)，其中h是BST的高度。
Notice
保证p是给定二叉树中的一个节点。(您可以直接通过内存地址找到p)
472.二叉树的路径和3
描述
给一棵二叉树和一个目标值，找到二叉树上所有的和为该目标值的路径。路径可以从二叉树的任意节点出发，任意节点结束。
样例
给一棵这样的二叉树：
1/ \2 3/
4
和目标值 target = 6。你需要返回的结果为：
[[2, 4],[2, 1, 3],[3, 1, 2],[4, 2]
]
475 二叉树的最大路径和2
描述
给一棵二叉树，找出从根节点出发的路径中，和最大的一条
这条路径可以在任何二叉树中的节点结束，但是必须包含至少一个点（也就是根了）
样例
给出如下的二叉树：
1/ \
2 3
返回4。(最大的路径为1→3)