记录一下最近遇到的几个二叉树的题型（附好用的遍历模板）

本文主要是介绍记录一下最近遇到的几个二叉树的题型（附好用的遍历模板），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

107. 二叉树的层序遍历 II

102. 二叉树的层序遍历

987. 二叉树的垂序遍历

以上三题可共用一个模板（dfs记录数的col和row)，不同之处就是使用哈希表的时候调整一下key和value：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:dic=defaultdict(list)def dfs(node,row,col):if node is None:returndic[col].append((row,node.val))dfs(node.left,row+1,col-1)dfs(node.right,row+1,col+1)dfs(root,0,0)ans=[]for _,i in sorted(dic.items()):i.sort()ans.append([j for _,j in i])return ans

145. 二叉树的后序遍历

144. 二叉树的前序遍历

94. 二叉树的中序遍历

二叉树的前中后序遍历虽然是很基础的算法，但是我看到了一个很有意思的解题思路，特此记录一下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:"""#方法一white,gray=0,1ans=[]stack=[(white,root)]while stack:color,node=stack.pop()if node is None:continueif color==white:stack.append((white,node.right))stack.append((gray,node))stack.append((white,node.left))else:ans.append(node.val)return ans"""#方法二ans=[]def mid(node):if node is not None:mid(node.left)ans.append(node.val)mid(node.right)mid(root)return ans

236. 二叉树的最近公共祖先

解题思路，先判断两个节点是否处于同一深度，如果不是同一深度，则让更深的节点向上移动至同一深度，随后两节点一同向上移动，直到两节点的父节点是同一节点时停止，这样就找到了最近公共祖先：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def find_depth(self, root, node):if not root:return 0if root == node:return 1left_depth = self.find_depth(root.left, node)right_depth = self.find_depth(root.right, node)if left_depth > 0:return left_depth + 1elif right_depth > 0:return right_depth + 1else:return 0def find_parent(self, root, node):if not root or not node:return Noneif root.left == node or root.right == node:return rootparent = self.find_parent(root.left, node)if not parent:parent = self.find_parent(root.right, node)return parentdef lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':depth_p, depth_q = self.find_depth(root, p), self.find_depth(root, q)while depth_p > depth_q:p = self.find_parent(root, p)depth_p -= 1while depth_q > depth_p:q = self.find_parent(root, q)depth_q -= 1while q != p:p = self.find_parent(root, p)q = self.find_parent(root, q)return p

这篇关于记录一下最近遇到的几个二叉树的题型（附好用的遍历模板）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---