二叉树

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