devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Leetcode算法题之二叉树模板_二叉树题目模板

作者：羊村懒王 | 2024-05-20 03:24:47

赞

踩

二叉树题目模板

一、树的定义

  1. # Definition for a binary tree node.
  2. class TreeNode:
  3.     def __init__(self, val=0, left=None, right=None):
  4.         self.val = val
  5.         self.left = left
  6.         self.right = right

二、树的遍历

基础知识

二叉树前序遍历的顺序为：

  1. 先遍历根节点；
  2. 随后递归地遍历左子树；
  3. 最后递归地遍历右子树。

二叉树中序遍历的顺序为：

  1. 先递归地遍历左子树；
  2. 随后遍历根节点；
  3. 最后递归地遍历右子树。

二叉树后序遍历的顺序为：

  1. 先递归地遍历左子树；
  2. 随后递归地遍历右子树；
  3. 最后遍历根节点。

对于任意一颗树而言，前序遍历的形式总是：

  • [ 根节点， [左子树的前序遍历结果]，[右子树的前序遍历结果] ]

中序遍历的形式总是：

  • [ [左子树的中序遍历结果]，根节点， [右子树的中序遍历结果] ]

后序遍历的形式总是：

  • [ [左子树的后序遍历结果]，[右子树的后序遍历结果]，根节点]

三、刷题模板

1、递归

  1. # 递归
  2. # 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。
  3. # 空间复杂度：空间复杂度：O(h)，h为树的高度。最坏情况下需要空间O(n)，平均情况为O(logn)
  4.  
  5. # 递归1：二叉树遍历最易理解和实现版本
  6. class Solution:
  7.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  8.         if not root:
  9.             return []
  10.         # 前序递归
  11.         return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
  12.         # # 中序递归 
  13.         # return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
  14.         # # 后序递归
  15.         # return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
  16.  
  17. # 递归2：通用模板，可以适应不同的题目，添加参数、增加返回条件、修改进入递归条件、自定义返回值
  18. class Solution:
  19.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  20.         def dfs(cur):
  21.             if not cur:
  22.                 return      
  23.             # 前序递归
  24.             res.append(cur.val)
  25.             dfs(cur.left)
  26.             dfs(cur.right) 
  27.             # # 中序递归
  28.             # dfs(cur.left)
  29.             # res.append(cur.val)
  30.             # dfs(cur.right)
  31.             # # 后序递归
  32.             # dfs(cur.left)
  33.             # dfs(cur.right)
  34.             # res.append(cur.val)      
  35.         res = []
  36.         dfs(root)
  37.         return res

2、迭代

  1. # 迭代
  2. # 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。
  3. # 空间复杂度：O(h)，h为树的高度。取决于树的结构，最坏情况存储整棵树，即O(n)
  4.  
  5. # 迭代1：前序遍历最常用模板（后序同样可以用）
  6. class Solution:
  7.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  8.         if not root:
  9.             return []        
  10.         res = []
  11.         stack = [root]
  12.         # # 前序迭代模板：最常用的二叉树DFS迭代遍历模板
  13.         while stack:
  14.             cur = stack.pop()
  15.             res.append(cur.val)
  16.             # 由于栈是“先进后出”的顺序，所以入栈时先将右子树入栈，这样使得前序遍历结果为 “根->左->右”的顺序。
  17.             if cur.right:
  18.                 stack.append(cur.right)
  19.             if cur.left:
  20.                 stack.append(cur.left)
  21.         return res
  22.         
  23.         # # 后序迭代，相同模板：将前序迭代进栈顺序稍作修改，最后得到的结果反转
  24.         # while stack:
  25.         #     cur = stack.pop()
  26.         #     if cur.left:
  27.         #         stack.append(cur.left)
  28.         #     if cur.right:
  29.         #         stack.append(cur.right)
  30.         #     res.append(cur.val)
  31.         # return res[::-1]
  32.  
  33. # 迭代1：层序遍历最常用模板
  34. class Solution:
  35.     def levelOrder(self, root: TreeNode) -> List[List[int]]:
  36.         if not root:
  37.             return []
  38.         cur, res = [root], []
  39.         while cur:
  40.             lay, layval = [], []
  41.             for node in cur:
  42.                 layval.append(node.val)
  43.                 if node.left: lay.append(node.left)
  44.                 if node.right: lay.append(node.right)
  45.             cur = lay
  46.             res.append(layval)
  47.         return res
  48.  
  49.         
  50.         
  51. # 迭代2：前、中、后序遍历通用模板（只需一个栈的空间）
  52. class Solution:
  53.     def inorderTraversal(self, root: TreeNode) -> List[int]: 
  54.         res = []
  55.         stack = []
  56.         cur = root
  57.         # 中序，模板：先用指针找到每颗子树的最左下角，然后进行进出栈操作
  58.         while stack or cur:
  59.             while cur:
  60.                 stack.append(cur)
  61.                 cur = cur.left
  62.             cur = stack.pop()
  63.             res.append(cur.val)
  64.             cur = cur.right
  65.         return res
  66.         
  67.         # # 前序，相同模板
  68.         # while stack or cur:
  69.         #     while cur:
  70.         #         res.append(cur.val)
  71.         #         stack.append(cur)
  72.         #         cur = cur.left
  73.         #     cur = stack.pop()
  74.         #     cur = cur.right
  75.         # return res
  76.         
  77.         # # 后序，相同模板
  78.         # while stack or cur:
  79.         #     while cur:
  80.         #         res.append(cur.val)
  81.         #         stack.append(cur)
  82.         #         cur = cur.right
  83.         #     cur = stack.pop()
  84.         #     cur = cur.left
  85.         # return res[::-1]
  86.         
  87.  
  88.  
  89. # 迭代3：标记法迭代（需要双倍的空间来存储访问状态）：
  90. # 前、中、后、层序通用模板，只需改变进栈顺序或即可实现前后中序遍历，
  91. # 而层序遍历则使用队列先进先出。0表示当前未访问，1表示已访问。
  92. class Solution:
  93.     def preorderTraversal(self, root: TreeNode) -> List[int]:
  94.         res = []
  95.         stack = [(0, root)]
  96.         while stack:
  97.             flag, cur = stack.pop()
  98.             if not cur: continue
  99.             if flag == 0:
  100.                 # 前序，标记法
  101.                 stack.append((0, cur.right))
  102.                 stack.append((0, cur.left))
  103.                 stack.append((1, cur))
  104.                 
  105.                 # # 后序，标记法
  106.                 # stack.append((1, cur))
  107.                 # stack.append((0, cur.right))
  108.                 # stack.append((0, cur.left))
  109.                 
  110.                 # # 中序，标记法
  111.                 # stack.append((0, cur.right))
  112.                 # stack.append((1, cur))
  113.                 # stack.append((0, cur.left))  
  114.             else:
  115.                 res.append(cur.val)  
  116.         return res
  117.         
  118.         # # 层序，标记法
  119.         # res = []
  120.         # queue = [(0, root)]
  121.         # while queue:
  122.         #     flag, cur = queue.pop(0)  # 注意是队列，先进先出
  123.         #     if not cur: continue
  124.         #     if flag == 0:
  125.                   # 层序遍历这三个的顺序无所谓，因为是队列，只弹出队首元素
  126.         #         queue.append((1, cur))
  127.         #         queue.append((0, cur.left))
  128.         #         queue.append((0, cur.right))
  129.         #     else:
  130.         #         res.append(cur.val)
  131.         # return res

3、莫里斯遍历

  1. # 莫里斯遍历
  2. # 时间复杂度：O(n)，n为节点数，看似超过O(n)，有的节点可能要访问两次，实际分析还是O(n)，具体参考大佬博客的分析。
  3. # 空间复杂度：O(1)，如果在遍历过程中就输出节点值，则只需常数空间就能得到中序遍历结果，空间只需两个指针。
  4. # 如果将结果储存最后输出，则空间复杂度还是O(n)。
  5.  
  6. # PS：莫里斯遍历实际上是在原有二叉树的结构基础上，构造了线索二叉树，
  7. # 线索二叉树定义为：原本为空的右子节点指向了中序遍历顺序之后的那个节点，把所有原本为空的左子节点都指向了中序遍历之前的那个节点
  8. # emmmm，好像大学教材学过，还考过
  9.  
  10. # 此处只给出中序遍历，前序遍历只需修改输出顺序即可
  11. # 而后序遍历，由于遍历是从根开始的，而线索二叉树是将为空的左右子节点连接到相应的顺序上，使其能够按照相应准则输出
  12. # 但是后序遍历的根节点却已经没有额外的空间来标记自己下一个应该访问的节点，
  13. # 所以这里需要建立一个临时节点dump，令其左孩子是root。并且还需要一个子过程，就是倒序输出某两个节点之间路径上的各个节点。
  14. # 具体参考大佬博客
  15.  
  16. # 莫里斯遍历，借助线索二叉树中序遍历（附前序遍历）
  17. class Solution:
  18.     def inorderTraversal(self, root: TreeNode) -> List[int]:
  19.         res = []
  20.         # cur = pre = TreeNode(None)
  21.         cur = root
  22.  
  23.         while cur:
  24.             if not cur.left:
  25.                 res.append(cur.val)
  26.                 # print(cur.val)
  27.                 cur = cur.right
  28.             else:
  29.                 pre = cur.left
  30.                 while pre.right and pre.right != cur:
  31.                     pre = pre.right
  32.                 if not pre.right:
  33.                     # print(cur.val) 这里是前序遍历的代码，前序与中序的唯一差别，只是输出顺序不同
  34.                     pre.right = cur
  35.                     cur = cur.left
  36.                 else:
  37.                     pre.right = None
  38.                     res.append(cur.val)
  39.                     # print(cur.val)
  40.                     cur = cur.right
  41.         return res

4.N叉树遍历

  1. # N叉树遍历
  2. # 时间复杂度：时间复杂度：O(M)，其中 M 是 N 叉树中的节点个数。每个节点只会入栈和出栈各一次。
  3. # 空间复杂度：O(M)。在最坏的情况下，这棵 N 叉树只有 2 层，所有第 2 层的节点都是根节点的孩子。
  4. # 将根节点推出栈后，需要将这些节点都放入栈，共有 M−1个节点，因此栈的大小为 O(M)。
  5.  
  6.  
  7. """
  8. # Definition for a Node.
  9. class Node:
  10.     def __init__(self, val=None, children=None):
  11.         self.val = val
  12.         self.children = children
  13. """
  14.  
  15. # N叉树简洁递归
  16. class Solution:
  17.     def preorder(self, root: 'Node') -> List[int]:
  18.         if not root: return []
  19.         res = [root.val]
  20.         for node in root.children:
  21.             res.extend(self.preorder(node))
  22.         return res
  23.  
  24. # N叉树通用递归模板
  25. class Solution:
  26.     def preorder(self, root: 'Node') -> List[int]:
  27.         res = []
  28.         def helper(root):
  29.             if not root:
  30.                 return
  31.             res.append(root.val)
  32.             for child in root.children:
  33.                 helper(child)
  34.         helper(root)
  35.         return res
  36.  
  37. # N叉树迭代方法
  38. class Solution:
  39.     def preorder(self, root: 'Node') -> List[int]:
  40.         if not root:
  41.             return []
  42.         s = [root]
  43.         # s.append(root)
  44.         res = []
  45.         while s:
  46.             node = s.pop()
  47.             res.append(node.val)
  48.             # for child in node.children[::-1]:
  49.             #     s.append(child)
  50.             s.extend(node.children[::-1])
  51.         return res
  52.

四、案例

树的深度

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def maxDepth(self, root: Optional[TreeNode]) -> int:
  9.         if not root: 
  10.             return 0
  11.  
  12.         return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
  13.  
  14.  
  15.  
  16.  
  17. # 层序遍历
  18. # Definition for a binary tree node.
  19. # class TreeNode:
  20. #     def __init__(self, val=0, left=None, right=None):
  21. #         self.val = val
  22. #         self.left = left
  23. #         self.right = right
  24. class Solution:
  25.     def maxDepth(self, root: Optional[TreeNode]) -> int:
  26.         if not root:
  27.             return 0
  28.         
  29.         cur, res = [root], 0
  30.         while cur:
  31.             layer, tmp = [], []
  32.             for info in cur:
  33.                 tmp.append(info.val)
  34.                 if info.left:
  35.                     layer.append(info.left)
  36.                 if info.right:
  37.                     layer.append(info.right)
  38.             
  39.             cur = layer
  40.             res+=1
  41.  
  42.         return res

公共祖先

  1. """
  2. p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
  3. p = root ，且 q 在 root 的左或右子树中；
  4. q = root ，且 p 在 root 的左或右子树中；
  5. """
  6. class Solution:
  7.     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
  8.         if not root or root == q or root == p:
  9.             return root
  10.  
  11.         left = self.lowestCommonAncestor(root.left, p, q)
  12.         right = self.lowestCommonAncestor(root.right, p, q)
  13.         if not left and not right: return 
  14.         if not left: return right
  15.         if not right: return left
  16.         return root

112. 路径总和

  1. class Solution:
  2.     def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
  3.         if not root:
  4.             return False
  5.  
  6.         if not root.left and not root.right:
  7.             return targetSum == root.val
  8.  
  9.         return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

98. 验证二叉搜索树

  1. class Solution:
  2.     # 中序遍历时，判断当前节点是否大于中序遍历的前一个节点，如果大于，说明满足 BST，继续遍历；否则直接返回 false。
  3.     # 中序遍历为升序
  4.     pre = float("-inf")
  5.  
  6.     def isValidBST(self, root: Optional[TreeNode]) -> bool:
  7.         if root == None: return True
  8.  
  9.         if not self.isValidBST(root.left):
  10.             return False
  11.  
  12.         if root.val <= self.pre:
  13.             return False
  14.  
  15.         self.pre = root.val
  16.         return self.isValidBST(root.right)

参考

题目：

144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
102. 二叉树的层序遍历
589. N叉树的前序遍历

资料：

LeetCode官方题解
powcai的题解
Grandyang的博客
Annie Kim's Blog
维基百科对于线索二叉树的解释
莫里斯的文章

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/595882
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号