二叉树
(1) 中序遍历
"""
给定一个二叉树的根节点 root，返回它的中序遍历。
"""
def inorderTraversal(self, root):""":type root: Optional[TreeNode]:rtype: List[int]"""res = []self.order(root, res)return resdef order(self, root, res):if not root:return Noneself.order(root.left, res)res.append(root.val)self.order(root.right, res)
(2) 最大深度
"""
给定一个二叉树 root，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
"""
def maxDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""if not root:return 0left = self.maxDepth(root.left)right = self.maxDepth(root.right)return max(left, right)+1
(3) 翻转二叉树
"""
给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。
"""
def invertTree(self, root):""":type root: Optional[TreeNode]:rtype: Optional[TreeNode]"""if not root:return Noneleft = self.invertTree(root.left)right = self.invertTree(root.right)root.left, root.right = right, leftreturn root
(4) 对称二叉树
"""
给你一个二叉树的根节点 root，检查它是否轴对称。
"""
def isSymmetric(self, root):""":type root: Optional[TreeNode]:rtype: bool"""return self.treesame(root.left, root.right)def treesame(self, p, q):if p is None or q is None:return p is qreturn p.val == q.val and self.treesame(p.left, q.right) and self.treesame(p.right, q.left)
(5) 二叉树的直径
"""
给你一棵二叉树的根节点，返回该树的直径。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root。两节点之间路径的长度由它们之间边数表示。
"""
res = 0def dfs(node):if node is None:return -1l_len = dfs(node.left) + 1r_len = dfs(node.right) + 1nonlocal resres = max(res, l_len + r_len)return max(l_len, r_len)dfs(root)
return res
(6) 二叉树的层序遍历
"""
给你二叉树的根节点 root，返回其节点值的层序遍历 。 （即逐层地，从左到右访问所有节点）。
"""
if not root: return []
res = []
queue = collections.deque()
queue.append(root)
while queue:tmp = []for _ in range(len(queue)):node = queue.popleft()tmp.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(tmp)
return res
(7) 将有序数组转换为二叉搜索树
"""
给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。
"""
def sortedArrayToBST(self, nums):def makeTree(start, end):if start > end:returnmid = (start+end) // 2midtree = TreeNode(nums[mid])midtree.left = makeTree(start, mid-1)midtree.right = makeTree(mid+1, end)return midtreereturn makeTree(0, len(nums)-1)
(8) 验证二叉搜索树
"""
给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。
"""
def isValidBST(self, root):def dfs(node, min_val, max_val):if not node:return Trueif not min_val < node.val < max_val:return Falsereturn dfs(node.left, min_val, node.val) and dfs(node.right, node.val, max_val)return dfs(root, float('-inf'), float('inf'))
(9) 二叉搜索树中第 k 小的元素
"""
给定一个二叉搜索树的根节点 root，和一个整数 k，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。
"""
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:def dfs(node):if not node or self.k == 0:returndfs(node.left)self.k -= 1if self.k == 0:self.res = node.valdfs(node.right)self.k = kdfs(root)return self.res
(10) 二叉树的右视图
"""
给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
"""
if not root:return []
queue = collections.deque()
queue.append(root)
res = []
while queue:for _ in range(len(queue)):node = queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(node.val)
return res
(11) 二叉树展开为链表
"""
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null。展开后的单链表应该与二叉树先序遍历顺序相同。
"""
nodes = []def preorder(node):if not node:return Nonenodes.append(node)preorder(node.left)preorder(node.right)preorder(root)
for i in range(len(nodes)-1):nodes[i].left = Nonenodes[i].right = nodes[i+1]
(12) 从前序和中序遍历构造二叉树
"""
给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
"""
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:if not preorder:return Noneleft_size = inorder.index(preorder[0])# 左子树有 left_size 个节点left = self.buildTree(preorder[1:1+left_size], inorder[:left_size])right = self.buildTree(preorder[1+left_size:], inorder[1+left_size:])return TreeNode(preorder[0], left, right)
(13) 路径总和 III
"""
给定一个二叉树的根节点 root，和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum 的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
"""
if not root:return 0
cnt = collections.defaultdict(int)
cnt[0] = 1
presum = 0
res = 0
def dfs(node, presum):if not node:return presum += node.valnonlocal resres += cnt[presum-targetSum]cnt[presum] += 1dfs(node.left, presum)dfs(node.right, presum)cnt[presum] -= 1
dfs(root, presum)
return res
(14) 二叉树的最近公共祖先
"""
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
"""
# 找到 p 或 q 就有节点返回
if not root or root is q or root is p:return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:return root
return left if left else right
(15) 二叉树中的最大路径和
"""
路径和 是路径中各节点值的总和，给你一个二叉树的根节点 root，返回其最大路径和 。
"""
res = float("-inf")
def dfs(node):if not node:return 0left = dfs(node.left)right = dfs(node.right)nonlocal resres = max(res, left+right+node.val)return max(left+node.val, right+node.val, 0)
dfs(root)
return res