1，二叉树的定义
二叉树的结构：二叉树由根节点和左右子树组成，二叉树的左子树和右子树分别为二叉树。这种结构使得有关二叉树的问题大部分可以用递归的算法解决。
2，二叉树的序列化，使得内存中的二叉树可以在文件中存储起来。
二叉树的遍历有：前序，中序，后序遍历，层序遍历。
前序遍历（根节点->左子树->右子树）
中序遍历（左子树->根节点->右子树）
后序遍历（左子树->右子树->根节点）
层序遍历二叉树，即从上到下，同层节点从左到右遍历每个节点。通常会借助“队列”这种数据结构，保证“先进先出”。
Python中的队列结构在标准库中，from collections import deque
3，二叉树的反序列化（重建二叉树）
"""从前序遍历序列和中序遍历序列构建二叉树（无重复元素）
Given preorder and inorder traversal of a tree,
construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
preorder第一个元素为root，
在inorder里面找到root，在它之前的为左子树（长l1），之后为右子树（长l2）。
preorder[1]到preorder[l1]为左子树,之后为右子树，分别递归。"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder:
return None
root = TreeNode(preorder[0])
loc = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1 : loc + 1], inorder[ : loc])
root.right = self.buildTree(preorder[loc+1 : ], inorder[loc+1: ])
return root
"从中序和后序序列构建二叉树"
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if not postorder:
return None
root=TreeNode(postorder[-1])
loc = inorder.index(postorder[-1])
#inorder[:loc]#左子树,长度为loc;postorder[:loc]
#inorder[loc+1:]#右子树postorder[loc:-1]
root.left = self.buildTree( inorder[:loc], postorder[:loc])
root.right = self.buildTree(inorder[loc+1:], postorder[loc:-1] )
return root
3,二叉树的镜像（可以用递归来做）
二叉树的镜像定义：源二叉树
8
/
6 10
/ \ /
5 7 9 11
镜像二叉树
8
/
10 6
/ \ /
11 9 7 5
4，判断一颗二叉树是否是对称的，注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。（可以用递归来做）
5，判断给定的二叉树是否是二叉搜索树
6.二叉树的最大深度leetcode T104
"""二叉树的最大深度(二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。)
leetcode T104
The maximum depth is the number of nodes
along the longest path from the root node down to the farthest leaf node.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"""
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
7.路径总和
"""路径总和
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.
Note: A leaf is a node with no children.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
if root.left == None and root.right == None:
return sum-root.val == 0
return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
8.路径总和II
"""路径总和II
Given a binary tree and a sum,
find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处T113"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res=[]#记录所有路径数字
path=[]#记录每一条路径上的数字
def help(root,sum,path):
if not root:
return []
if not root.left and not root.right and root.val == sum:
path.append(root.val)
res.append(path)
if root.left:
help(root.left,sum-root.val,path+[root.val])
if root.right:
help(root.right,sum-root.val,path+[root.val])
help(root,sum,path)
return res
另一种写法，等同于上面
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def help(root,s,v,target):
if not root:
return
if root.left is None and root.right is None and root.val == target:
s.append(root.val)
v.append(s)
if root.left:
help(root.left,s+[root.val],v,target-root.val)
if root.right:
help(root.right,s+[root.val],v,target-root.val)
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
s=[] #记录每一条路径上的数字
v=[] #记录所有路径数字
help(root,s,v,sum)
return v
9.二叉树的最小深度
"""
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.
Note: A leaf is a node with no children.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
left=self.minDepth(root.left)
right=self.minDepth(root.right)
if left and right:
return min(left,right)+1
else:#此时right，left至少有一个树为空
return left+right+1
2020年7月23日22:44:38
