首页  思维导图  详情

二叉树题目整理

2022-01-06 21:50:50   3  举报





AI智能生成

二叉树题目整理 python解法

程序员的世界

数据结构与算法

二叉树

Leetcode

Python

作者其他创作

大纲/内容

二叉树的遍历

前序遍历

144二叉树的前序遍历

class Solution:     def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:         if not root:             return []         stack = [root, ]         ret = []         while stack:             node = stack.pop()             ret.append(node.val)             if node.right:                 stack.append(node.right)             if node.left:                 stack.append(node.left)         return ret

589N叉树的前序遍历

class Solution:     def preorder(self, root: 'Node') -> List[int]:         if not root:             return []         stack = [root, ]         ret = []         while stack:             node = stack.pop()             ret.append(node.val)             for d in reversed(node.children):                 if d:                     stack.append(d)         return ret

后序遍历

145二叉树的后序遍历

class Solution:     def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:         if not root:             return []         stack = [root, ]         ret = []         while stack:             node = stack.pop()             ret.append(node.val)             if node.left:                 stack.append(node.left)             if node.right:                 stack.append(node.right)         return ret[::-1]

590N叉树的后序遍历

class Solution:     def postorder(self, root: 'Node') -> List[int]:         if not root:             return []         stack = [root, ]         ret = []         while stack:             node = stack.pop()             ret.append(node.val)             for d in node.children:                 if d:                     stack.append(d)         return ret[::-1]

94二叉树的中序遍历

class Solution:     def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:         stack = []         ret = []         curr = root         while curr or stack:             while curr:                 stack.append(curr)                 curr = curr.left             curr = stack.pop()             ret.append(curr.val)             curr = curr.right         return ret

二叉树的层序遍历

102二叉树的层序遍历

class Solution:     def levelOrder(self, root: TreeNode) -> List[List[int]]:         if not root:             return []         queue = [root, ]         ret = []         while queue:             path = []             length = len(queue)             for _ in range(length):                 node = queue.pop(0)                 path.append(node.val)                 if node.left:                     queue.append(node.left)                 if node.right:                     queue.append(node.right)             ret.append(path.copy())         return ret

107 二叉树的层次遍历II

199二叉树的右视图

637二叉树的层平均值

429N叉树的层序遍历

class Solution:     def levelOrder(self, root: 'Node') -> List[List[int]]:         if not root:             return []         queue = [root]         ret = []         while queue:             length = len(queue)             path = []             for i in range(length):                 node = queue.pop(0)                 path.append(node.val)                 for candidate_node in node.children:                     queue.append(candidate_node)             ret.append(path)         return ret

515在每个树行中找最大值

116填充每一个节点的下一个右侧节点指针（完美二叉树）

class Solution:     def connect(self, root: 'Node') -> 'Node':         if not root:             return root         queue = [root, ]         while queue:             length = len(queue)             for i in range(length):                 node = queue.pop(0)                 if i == 0:                     start = node                 else:                     start.next = node                     start = node                 if node.left:                     queue.append(node.left)                 if node.right:                     queue.append(node.right)         return root

117填充每一个节点的下一个右侧节点指针II（普通二叉树）

二叉树的属性

101 对称二叉树

递归

class Solution:     def isSymmetric(self, root: TreeNode) -> bool:         """         属于后序遍历         """         if not root:             return True         def dfs(node1, node2):             if not node1 and not node2:                 return True             elif not node1 and node2:                 return False             elif not node2 and node1:                 return False             elif node1.val != node2.val:                 return False             else:  # node.val == node2.val了                 outside_bool = dfs(node1.left, node2.right)                 inside_bool = dfs(node1.right, node2.left)                 return outside_bool and inside_bool         return dfs(root.left, root.right)

迭代

class Solution:     def isSymmetric(self, root: TreeNode) -> bool:         if not root:             return True         stack = [root.left, root.right]         while stack:             right_node = stack.pop()             left_node = stack.pop()             if not left_node and not right_node:                 continue             if (left_node and not right_node) or (right_node and not left_node) or (right_node.val != left_node.val):                 return False             else:                 stack.append(left_node.left)                 stack.append(right_node.right)                 stack.append(left_node.right)                 stack.append(right_node.left)         return True

100相同的树

递归

class Solution:     def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:         if not p and not q:             return True         if (p and not q) or (q and not p):             return False         return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

迭代

class Solution:     def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:         stack = [p, q]         while stack:             q = stack.pop()             p = stack.pop()             if not p and not q:                 continue             elif (p and not q) or (q and not p) or (p.val != q.val):                 return False             stack.extend([p.left, q.left, p.right, q.right])         return True

最大深度

104二叉树的最大深度

迭代法（层序遍历）

class Solution:     def maxDepth(self, root: TreeNode) -> int:         if not root:             return 0         queue = [root, ]         ret = 0         while queue:             path = []             length = len(queue)             for _ in range(length):                 node = queue.pop(0)                 path.append(node.val)                 if node.left:                     queue.append(node.left)                 if node.right:                     queue.append(node.right)             ret+=1         return ret

递归法

class Solution:     def maxDepth(self, root: TreeNode) -> int:         if not root:             return 0         return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

559N叉树的最大深度

递归法

class Solution:     def maxDepth(self, root: 'Node') -> int:         if not root:             return 0  # 注意sum里面空值（列表）会报错         return 1+(max(self.maxDepth(node) for node in root.children) if root.children else 0)

111二叉树的最小深度

迭代法（层序遍历）

class Solution:     def minDepth(self, root: TreeNode) -> int:         if not root:             return 0         queue = [root, ]         ret = 0         while queue:             length = len(queue)             for _ in range(length):                 node = queue.pop(0)                 if not node.left and not node.right:                     return ret+1                 if node.left:                     queue.append(node.left)                 if node.right:                     queue.append(node.right)             ret += 1         return ret

递归法

class Solution:     def minDepth(self, root: TreeNode) -> int:         if not root:             return 0         if not root.left:             return self.minDepth(root.right) + 1         if not root.right:             return self.minDepth(root.left) + 1         return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

222完全二叉树的节点个数

常规遍历法

class Solution:     def countNodes(self, root: TreeNode) -> int:         if not root:             return 0         stack = [root, ]         ret = []         while stack:             node = stack.pop()             ret.append(node.val)             if node.right:                 stack.append(node.right)             if node.left:                 stack.append(node.left)         return len(ret)

利用二叉树特性法

class Solution:     def countNodes(self, root: TreeNode) -> int:         if not root:             return 0         left = root.left         right = root.right         left_height = 0         right_height = 0         while left:             left = left.left             left_height += 1         while right:             right = right.right             right_height += 1         if left_height == right_height:             return 2 ** (left_height+1) - 1  # left_height是左子树深度，树深度要加1             # return (2 << left_height) - 1         else:             return 1 + self.countNodes(root.left) + self.countNodes(root.right)

110平衡二叉树

class Solution:     def isBalanced(self, root: TreeNode) -> bool:         if not root:             return True         def dfs(root):             if not root:                 return 0             return 1+max(dfs(root.left), dfs(root.right))         left = dfs(root.left)         right = dfs(root.right)         return abs(left-right) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

257二叉树的所有路径

回溯法

class Solution:     def binaryTreePaths(self, root: TreeNode) -> List[str]:         if not root:             return []         ret = []         def dfs(root, path):             if not root.left and not root.right:                 ret.append(path.copy())             else:                 for node in [root.left, root.right]:                     if node:                         dfs(node, path + [node.val, ])         path = [root.val]         dfs(root, path)         return ['->'.join([str(ii) for ii in i]) for i in ret]

404左叶子之和

递归法

class Solution:     def sumOfLeftLeaves(self, root: TreeNode) -> int:         if not root:             return 0         if root.left and not root.left.left and not root.left.right:             mid = root.left.val         else:             mid = 0         return mid + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

迭代法

class Solution:     def sumOfLeftLeaves(self, root: TreeNode) -> int:         if not root:             return 0         stack = [root, ]         ret = 0         while stack:             node = stack.pop()             if node.left and not node.left.left and not node.left.right:                 ret += node.left.val             if node.right:                 stack.append(node.right)             if node.left:                 stack.append(node.left)         return ret

513找树左下角的值

迭代法（层序遍历）

class Solution:     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:        queue = [root, ]        ret = []        while queue:            path = []            length = len(queue)            for _ in range(length):                node = queue.pop(0)                path.append(node.val)                if node.left:                    queue.append(node.left)                if node.right:                    queue.append(node.right)            ret.append(path.copy())        return ret[-1][0]

递归法

class Solution:     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:         self.ret = 0         self.max_depth = -1         def dfs(node, depth):             if not node.left and not node.right:                 if depth > self.max_depth:                     self.ret = node.val                     self.max_depth = depth                 return             if node.left:                 dfs(node.left, depth+1)             if node.right:                 dfs(node.right, depth+1)             return         dfs(root, 0)         return self.ret

112路径总和

递归法

class Solution:     def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:         if not root:             return False         if not root.left and not root.right:             return root.val == targetSum         return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum - root.val)

迭代法

113路径总和II

回溯法

class Solution:     def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:         if not root:             return []         ret, path = [], []         def dfs(node, path, sum_):             if not node.left and not node.right:                 if sum_ == node.val:                     ret.append(path + [node.val, ])             for i in [node.left, node.right]:                 if i:                     dfs(i, path + [node.val, ], sum_ - node.val)         dfs(root, path, targetSum)         return ret

二叉树的修改和构造

226翻转二叉树

递归版本

class Solution:     def invertTree(self, root: TreeNode) -> TreeNode:         if not root:             return root         def swap(p):             a = p.left             p.left = p.right             p.right = a         swap(root)         self.invertTree(root.left)         self.invertTree(root.right)         return root

迭代法

class Solution:      def invertTree(self, root: TreeNode) -> TreeNode:         def swap(node):             a = node.left             node.left = node.right             node.right = a         if not root:             return root         stack = [root, ]         while stack:             node = stack.pop()             swap(node)             if node.right:                 stack.append(node.right)             if node.left:                 stack.append(node.left)         return root

654最大二叉树

class Solution:     def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:         if not nums:             return None         if len(nums) == 1:             return TreeNode(nums[0])         max_ = max(nums)         index_ = nums.index(max_)         root = TreeNode(max_)         left = self.constructMaximumBinaryTree(nums[:index_])         right = self.constructMaximumBinaryTree(nums[index_+1:])         root.left = left         root.right = right         return root

617合并二叉树

递归（前中后序都可以）

class Solution:     def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:         if not root1:             return root2         if not root2:             return root1         root1.val += root2.val         root1.left = self.mergeTrees(root1.left, root2.left)         root1.right = self.mergeTrees(root1.right, root2.right)         return root1

迭代

class Solution:     def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:         if not root1:             return root2         if not root2:             return root1         stack = [root1, root2]         while stack:             node2 = stack.pop()             node1 = stack.pop()             node1.val += node2.val             if node1.left and node2.left:                 stack.append(node1.left)                 stack.append(node2.left)             if node1.right and node2.right:                 stack.append(node1.right)                 stack.append(node2.right)             if node2.left and not node1.left:                 node1.left = node2.left             if node2.right and not node1.right:                 node1.right = node2.right         return root1

105从中序和前序遍历序列构造二叉树

class Solution:     def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:         if not inorder:             return None         if len(preorder) == 1:             return TreeNode(preorder[0])         else:             root_val = preorder[0]             index_ = inorder.index(root_val)             left = self.buildTree(preorder[1:index_ + 1], inorder[:index_])             right = self.buildTree(preorder[index_ + 1:], inorder[index_ + 1:])             root = TreeNode(root_val)             root.left = left             root.right = right         return root

106从中序和后续遍历序列构造二叉树

class Solution:     def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:         if not postorder:             return None         if len(postorder) == 1:             return TreeNode(postorder[-1])         else:             root_val = postorder[-1]             index_ = inorder.index(root_val)             left = self.buildTree(inorder[:index_], postorder[:index_])             right = self.buildTree(inorder[index_+1:], postorder[index_:-1])             root = TreeNode(root_val)             root.left = left             root.right = right         return root

二叉搜索树的属性

700二叉搜索树中的搜索

递归法

初始写法（并不是搜索到结果就直接返回，全部遍历了）

class Solution:     def searchBST(self, root: TreeNode, val: int) -> TreeNode:         self.ret = None         def dfs(root, val):             if root and root.val == val:                 self.ret = root                 return             if not root:                 return None             if val > root.val:                 dfs(root.right, val)             else:                 dfs(root.left, val)         dfs(root, val)         return self.ret

新写法（搜到结果直接返回）

class Solution:     def searchBST(self, root: TreeNode, val: int) -> TreeNode:         if not root or root.val == val:             return root         if val > root.val:             return self.searchBST(root.right, val)         if val < root.val:             return self.searchBST(root.left, val)

迭代法

简洁版（不需栈，一条路遍历下去就行）

class Solution:     def searchBST(self, root: TreeNode, val: int) -> TreeNode:         while root:             if val > root.val:                 root = root.right             elif val < root.val:                 root = root.left             else:                 return root         return None

初始版

class Solution:     def searchBST(self, root: TreeNode, val: int) -> TreeNode:         if not root:             return root         stack = [root, ]         while stack:             node = stack.pop()             if node.val == val:                 return node             if node.right and val > node.val:                 stack.append(node.right)             if node.left and val < node.val:                 stack.append(node.left)         return None

98验证二叉搜索树

递归法

class Solution:     def __init__(self):         self.pre = float('-inf')     def isValidBST(self, root: TreeNode) -> bool:         if not root:             return True         left = self.isValidBST(root.left)         if not root.val > self.pre:             return False         else:             self.pre = root.val         right = self.isValidBST(root.right)         return left and right

迭代法

class Solution:     def isValidBST(self, root: TreeNode) -> bool:         stack = []         pre = float('-inf')         curr = root         while curr or stack:             while curr:                 stack.append(curr)                 curr = curr.left             curr = stack.pop()             if curr.val <= pre:                 return False             else:                 pre = curr.val             curr = curr.right         return True

530二叉搜索树中的最小绝对差

递归法

class Solution:     def __init__(self):         self.pre = float('-inf')         self.ret = float('inf')     def getMinimumDifference(self, root: TreeNode) -> int:         def dfs(root):             if not root:                 return             self.getMinimumDifference(root.left)             cur_ret = root.val - self.pre             self.ret = min(self.ret, cur_ret)             self.pre = root.val             self.getMinimumDifference(root.right)         dfs(root)         return self.ret

迭代法

stack = []         ret = float('inf')         curr = root         pre = float('-inf')         while curr or stack:             while curr:                 stack.append(curr)                 curr = curr.left             curr = stack.pop()             cur_value = curr.val - pre             # print(cur_value)             ret = min(ret, cur_value)             pre = curr.val             curr = curr.right         return ret

501二叉搜索树中的众数

递归法

class Solution:     def findMode(self, root: TreeNode) -> List[int]:         self.ret = []         self.pre = None         self.cur_count = 0         self.max_count = 0         def dfs(root):             if not root:                 return             dfs(root.left)             if not self.pre:                 self.cur_count = 1             elif self.pre.val == root.val:                 self.cur_count += 1             else:                 self.cur_count = 1             self.pre = root             if self.cur_count > self.max_count:                 self.ret.clear()                 self.max_count = self.cur_count                 self.ret.append(root.val)             elif self.cur_count == self.max_count:                 self.ret.append(root.val)             dfs(root.right)         dfs(root)         return self.ret

迭代法

class Solution:     def findMode(self, root: TreeNode) -> List[int]:         stack = []         ret = []         cur_count = 0         max_count = 0         pre = None         curr = root         while curr or stack:             while curr:                 stack.append(curr)                 curr = curr.left             curr = stack.pop()             if pre == None:                 cur_count = 1             elif pre.val == curr.val:                 cur_count += 1             else:                 cur_count = 1             pre = curr             if cur_count > max_count:                 ret.clear()                 ret.append(curr.val)                 max_count = cur_count             elif cur_count == max_count:                 ret.append(curr.val)             curr = curr.right         return ret

538把二叉搜索树转换为累加树

迭代

class Solution:     def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:         stack = []         curr = root         sum_ = 0         while curr or stack:             while curr:                 stack.append(curr)                 curr = curr.right             curr = stack.pop()             sum_ += curr.val             curr.val = sum_             curr = curr.left         return root

递归

class Solution:     def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:         self.pre = 0         def dfs(root):             if not root:                 return             dfs(root.right)             root.val += self.pre             self.pre = root.val             dfs(root.left)         dfs(root)         return root

二叉树的公共祖先

236二叉树的最近公共祖先

递归法（后序遍历）

class Solution:     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':         if root == p or root == q or not root:             return root         left = self.lowestCommonAncestor(root.left, p, q)         right = self.lowestCommonAncestor(root.right, p, q)         if left and right:             return root         elif not left and right:             return right         elif not right and left:             return left         else:  # left=None and right=None             return None

236二叉搜索树的最近公共祖先

递归法

class Solution:     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':         if root.val < q.val and root.val < p.val:             return self.lowestCommonAncestor(root.right, p, q)         elif root.val > q.val and root.val > p.val:             return self.lowestCommonAncestor(root.left, p, q)         else:             return root

迭代法

class Solution:     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':         if p.val < q.val:             p, q = q, p         while root:             if p.val <= root.val <= q.val:                 return root             elif root.val > q.val:                 root = root.left             elif root.val < p.val:                 root = root.righ

二叉搜索树的修改与构造

701二叉搜索树中的插入操作

递归法

class Solution:     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:         if not root:             return TreeNode(val)         if val > root.val:             root.right = self.insertIntoBST(root.right, val)         if val < root.val:             root.left = self.insertIntoBST(root.left, val)         return root

迭代法

class Solution:     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:         if not root:             return TreeNode(val)         ret = root         while root:             pre = root             if val > root.val:                 root = root.right             elif val < root.val:                 root = root.left         if pre.val > val:             pre.left = TreeNode(val)         if pre.val < val:             pre.right= TreeNode(val)         return ret

450删除二叉搜索树中的节点

递归

class Solution:     def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:         if not root:             return None         if root.val == key:             if not root.left:                 return root.right             elif not root.right:                 return root.left             else:                 temp = root                 root = root.right                 while root.left:                     root = root.left                 root.left = temp.left                 return temp.right         if key < root.val:             root.left = self.deleteNode(root.left, key)         elif key > root.val:             root.right = self.deleteNode(root.right, key)         return root

669修剪二叉搜索树

递归

class Solution:     def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:         if not root:             return None         if root.val < low:             return self.trimBST(root.right, low, high)         if root.val > high:             return self.trimBST(root.left, low, high)         root.left = self.trimBST(root.left, low, high)         root.right = self.trimBST(root.right, low, high)         return root

108将有序数组转换为二叉搜索树

递归

class Solution:     def sortedArrayToBST(self, nums: List[int]) -> TreeNode:         if not nums:             return None         if len(nums) == 1:             return TreeNode(nums[0])         mid = len(nums) // 2         root = TreeNode(nums[mid])         root.left = self.sortedArrayToBST(nums[:mid])         root.right = self.sortedArrayToBST(nums[mid+1:])         return root