关于树的算法总结

二叉树的题目普遍可以用递归和迭代的方式解决
树.jpg

我的新书《LangChain编程从入门到实践》 已经开售!推荐正在学习AI应用开发的朋友购买阅读!
LangChain编程从入门到实践

  • 其他分类方式
    树的分类2.jpg

    基础算法

    二叉树的最小深度

    1
    2
    3
    4
    5
    6
    7
    8
    class Solution:
    def minDepth(self, root: TreeNode) -> int:
    if not root:
    return 0
    if root.left==None or root.right==None:
    return self.minDepth(root.left)+self.minDepth(root.right)+1
    else:
    return min(map(self.minDepth,(root.left,root.right)))+1

    完全二叉树中节点的个数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # 深度遍历(递归法)
    class Solution:
    def countNodes(self, root: TreeNode) -> int:
    return 1+self.countNodes(root.left)+self.countNodes(root.right) if root else 0
    # 广度遍历(层序)
    class Solution:
    def countNodes(self, root: TreeNode) -> int:
    count=0
    if root:
    level=[root]
    while level:
    count+=len(level)
    level=[kid for node in level for kid in (node.left,node.right) if kid]
    return count

    二叉树的层平均值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
    average=[]
    if root:
    level=[root]
    while level:
    average.append(sum(i.val for i in level)/len(level))
    level=[kid for node in level for kid in (node.left,node.right) if kid]
    return average

    二叉树的直径

  • 采用分治和递归的思想:根节点为root的二叉树的直径 = max(root-left的直径, root->right的直径,root->left的最大深度+root->right的最大深度+1)
  • 分两种情况,1,最大直径经过根节点,则直径为左子树最大深度+右子树最大深度 2.如果不经过根节点,则取左子树或右子树的最大深度
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
    self.diameter=0
    def dfs(root):
    if root==None:
    return 0
    left=dfs(root.left)
    right=dfs(root.right)
    self.diameter=max(self.diameter,left+right)
    return max(left,right)+1
    dfs(root)
    return self.diameter

    判断二叉树是否是平衡二叉树

  • #一般认为平衡二叉树空间复杂度是O(logn)的,这是因为平衡二叉树的高度h就是O(logn)级别的。但是对于一般的树,严谨起见,还是要说O(h)的。这个h可能是logn(最好情况),也可能是n(最坏情况))
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
    def check_depth(root):
    if root==None:
    return 0
    left_depth=check_depth(root.left)
    right_depth=check_depth(root.right)
    return max(left_depth,right_depth)+1
    if root==None:
    return True
    return abs(check_depth(root.left)-check_depth(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

    两个二叉树是否完全相同

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
    if p and q:
    # 两棵二叉树均不为空,如果根节点的值相等,左子树相等和右子树相等,则这两棵二叉树相等,否则不相等。
    return p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
    return p is q
    # 最后一句相当于以下两种情况
    if not p and not q: # 两棵树均为空
    return True
    if not p and q or not q and p: # 两棵树只有一棵为空
    return False

    对称二叉树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
    def isSym(l,r):
    # 左右节点同时为空
    if not l and not r:
    return True
    # 左右节点相等,继续递归求解是否为镜像
    if l and r and l.val==r.val:
    return isSym(l.left,r.right) and isSym(l.right,r.left)
    # 其他情况均不是对称树
    return False
    return isSym(root,root)

    两个二叉树的最低公共祖先节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 思路:递归,如果当前节点就是p或q,说明当前节点就是最近的祖先;如果当前节点不是p或p,就试着从左右子树里找pq;如果pq分别在一左一右被找到,那么当前节点还是最近的祖先返回root就好了;否则,返回它们都在的那一边。
    class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if root==None:
    return
    if root==p or root==q:
    return root
    left=self.lowestCommonAncestor(root.left,p,q)
    right=self.lowestCommonAncestor(root.right,p,q)
    if left and right:
    return root
    if left:
    return left
    if right:
    return right
    else:
    return

    四种遍历方式

  • 二叉树的四种遍历方式分别是:前序、中序、后序和层次。它们的时间复杂度都是O(n),其中n是树中节点个数,因为每一个节点在递归的过程中,只访问了一次。
  • 三种深度优先遍历方法的空间复杂度是O(h),其中h是二叉树的深度,额外空间是函数递归的调用栈产生的,而不是显示的额外变量。空间复杂度,通常是指完成算法所用的辅助空间的复杂度,而不用管算法前置的空间复杂度。比如在树的遍历算法中,整棵树肯定要占O(n)的空间,n是树中节点的个数,这部分空间是“平凡”的,即肯定存在的,我们不讨论它。
  • 层次遍历的空间复杂度是O(w),其中w是二叉树的宽度(拥有最多节点的层的节点数)。
    树的遍历.png

    二叉树的前序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    # 递归解法
    class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
    ret=[]
    if root:
    ret=ret+[root.val]
    ret=ret+self.preorderTraversal(root.left)
    ret=ret+self.preorderTraversal(root.right)
    return ret
    # 迭代算法思路:使用栈的思想,从根节点开始以此使用ret添加根节点值,stack添加右节点,curr=左节点,如果左节点为None,则获取其上一个右节点(一直输出根节点,添加其右节点,遍历左节点,右节点的输出顺序为从下往上)
    class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
    ret=[]
    if root==None:
    return ret
    stack=[]
    curr=root
    while curr or stack:
    if curr:
    ret.append(curr.val)
    stack.append(curr.right)
    curr=curr.left
    else:
    curr=stack.pop()
    return ret

    二叉树的中序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    # 递归解法同上
    # 迭代解法
    class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
    res=[]
    if root==None:
    return res
    stack=[] #添加根节点
    curr=root
    while curr or stack:
    if curr:
    stack.append(curr)
    curr=curr.left
    else:
    curr=stack.pop()
    res.append(curr.val)
    curr=curr.right
    return res

    二叉树的后序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 递归解法同上
    # 迭代算法思路:后序遍历方式为:左右中,将其进行反转 中右左,那么我们可以实现一个中右左,其原理与前序遍历一样
    class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
    ret=[]
    if root==None:
    return ret
    stack=[]
    curr=root
    while curr or stack:
    if curr:
    ret.append(curr.val)
    stack.append(curr.left)
    curr=curr.right
    else:
    curr=stack.pop()
    return ret[::-1]

    二叉树的层次遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
    level=[root]
    ret=[]
    if root==None:
    return []
    while level:
    ret.append([i.val for i in level])
    level=[kid for node in level for kid in (node.left,node.right) if kid]
    return ret

    进阶算法

    不同的二叉树

  • 分析:采用动态规划解决,假设用G(n)表示前n个整数的二叉搜索树的总数,F(i)表示 当i节点为根节点的二叉搜索树的个数,当i为根节点时,由于二叉搜索树的规则,前i-1个节点都应该位于以i节点为根节点的左子树,i+1以后的节点都应该位于右子树,那么由咱们的假设可知,由前i-1个节点构成的左子树的二叉搜索树的总数为G(i-1),同理右子树的二叉搜索树的总数为G(n-i),所以以i为根节点的二叉搜索树的总数F(i) = G(i-1)*G(n-i),则前n个节点的所有二叉搜索树总数G(n) = F(1)+F(2)+…+F(n)。可以采用动态规划完成。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution:
    def numTrees(self, n: int) -> int:
    # n=0,n=1的情况
    g=[1,1]
    for i in range(2,n+1):
    f=0
    for j in range(1,i+1):
    #若i为3:g[0]*g[3]+g[1]*g[2]+g[2]*g[1]+g[3]*g[0]
    f+=g[j-1]*g[i-j]
    g.append(f)
    return g[-1]

    验证二叉搜索树(BST)

  • 一棵BST定义为:节点的左子树中的值要严格小于该节点的值,节点的右子树中的值要严格大于该节点的值,左右子树也必须是二叉查找树,一个节点的树也是二叉查找树。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
    output=[]
    self.inOrder(root,output)
    for i in range(1,len(output)):
    if output[i-1]>=output[i]:
    return False
    return True
    def inOrder(self,root,output):
    if root==None:
    return
    # 利用中序遍历,自下而上升序排列
    self.inOrder(root.left,output)
    output.append(root.val)
    self.inOrder(root.right,output)

    前序遍历和中序遍历构造二叉树(实现参考

  • 前序的第一个节点必定是根节点,在中序遍历中找到根节点所在的索引x,观察研究可以发现,在中序遍历中根节点索引之前的即为其左孩子,即左孩子们 = root[:x];那么在前序遍历中的左孩子个数和中序遍历是一样的,即为从前序遍历中索引为1(索引0为根节点)到x+1的节点;其余的则为右孩子们。
    最后递归调用自己,得到二叉树
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    if preorder==[]:
    return None
    # 找到根节点在中序遍历中的位置(索引)
    index=inorder.index(preorder[0])
    root = TreeNode(preorder[0])
    # 递归调用
    root.left=self.buildTree(preorder[1:index+1],inorder[0:index])
    root.right=self.buildTree(preorder[index+1:],inorder[index+1:])
    return root

关于树的算法总结

https://liduos.com/binary-tree.html

作者

莫尔索

发布于

2020-07-12

更新于

2024-05-24

许可协议

评论