行业知识
【leetcode刷题之路】面试经典150题（5）——二叉树+二叉树层次遍历+二叉搜索树
文章目录
- 9 二叉树
- 9.1 【递归】二叉树的最大深度
- 9.2 【递归】相同的树
- 9.3 【递归】翻转二叉树
- 9.4 【递归】对称二叉树
- 9.5 【递归】从前序与中序遍历序列构造二叉树
- 9.6 【递归】从中序与后序遍历序列构造二叉树
- 9.7 【BFS】填充每个节点的下一个右侧节点指针 II
- 9.8 【递归】二叉树展开为链表
- 9.9 【DFS】路径总和
- 9.10 【DFS】求根节点到叶节点数字之和
- 9.11 【BFS】【动态规划】二叉树中的最大路径和
- 9.12 【BFS】二叉搜索树迭代器
- 9.13 【BFS】完全二叉树的节点个数
- 9.14 【递归】二叉树的最近公共祖先
- 10 二叉树层次遍历
- 10.1 【DFS】二叉树的右视图
- 10.2 【BFS】二叉树的层平均值
- 10.3 【BFS】二叉树的层序遍历
- 10.4 【BFS】二叉树的锯齿形层序遍历
- 11 二叉搜索树
- 11.1 【BFS】二叉搜索树的最小绝对差
- 11.2 【BFS】二叉搜索树中第K小的元素
- 11.3 【BFS】【递归】验证二叉���索树
9 二叉树
9.1 【递归】二叉树的最大深度
题目地址：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150
（）递归找左子树和右子树的最大深度，就是二叉树的最大深度。
# 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 = rightclass Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 else: left_depth = self.maxDepth(root.left) right_depth = self.maxDepth(root.right) return max(left_depth, right_depth) + 1
9.2 【递归】相同的树
题目地址：https://leetcode.cn/problems/same-tree/description/?envType=study-plan-v2&envId=top-interview-150
（）左右子树相同的标志是左右子树都存在，且根节点的值相等，按照这一标准递归遍历树的左右子树。
# 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 = rightclass Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if (not p and q) or (p and not q): return False elif not p and not q: return True elif p.val != q.val: return False else: return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
9.3 【递归】翻转二叉树
题目地址：https://leetcode.cn/problems/invert-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150
详见代码。
# 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 = rightclass Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return root.left,root.right = self.invertTree(root.right),self.invertTree(root.left) return root
9.4 【递归】对称二叉树
题目地址：https://leetcode.cn/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-interview-150
详见代码。
# 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 = rightclass Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: return True return self.is_symmetric(root.left, root.right) def is_symmetric(self, left: TreeNode, right: TreeNode): if not left and not right: return True elif (not left or not right) or (left.val != right.val): return False else: return self.is_symmetric(left.left, right.right) and self.is_symmetric(left.right, right.left)
9.5 【递归】从前序与中序遍历序列构造二叉树
题目地址：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150
详见代码，找到根节点的位置进行递归。
# 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 = rightclass Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: if not preorder or not inorder: return root = TreeNode(preorder[0]) idx = inorder.index(preorder[0]) root.left = self.buildTree(preorder[1:1+idx],inorder[:idx]) root.right = self.buildTree(preorder[1+idx:],inorder[idx+1:]) return root
9.6 【递归】从中序与后序遍历序列构造二叉树
题目地址：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150
详见代码，找到根节点的位置进行递归。
# 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 = rightclass Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: if not inorder or not postorder: return root = TreeNode(postorder[-1]) idx = inorder.index(postorder[-1]) root.left = self.buildTree(inorder[:idx],postorder[:idx]) root.right = self.buildTree(inorder[1+idx:],postorder[idx:-1]) return root
9.7 【BFS】填充每个节点的下一个右侧节点指针 II
题目地址：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/?envType=study-plan-v2&envId=top-interview-150
其实就是找出每一层的所有结点就行了，而每一层的左右节点就是下一层的结点，按照这个规则进行BFS。
"""# Definition for a Node.class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next"""class Solution: def connect(self, root: 'Node') -> 'Node': if not root: return root def BFS(curLayer): nextLayer = [] for node in curLayer: if node.left: nextLayer.append(node.left) if node.right: nextLayer.append(node.right) if len(nextLayer) > 1: for i in range(0,len(nextLayer)-1): nextLayer[i].next = nextLayer[i+1] if nextLayer: BFS(nextLayer) BFS([root]) return root
9.8 【递归】二叉树展开为链表
题目地址：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-interview-150
二叉树的先序遍历的变形。
# 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 = rightclass Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ while root: if root.left: cur_left = root.left while cur_left.right: cur_left = cur_left.right cur_left.right = root.right root.right = root.left root.left = None root = root.right
9.9 【DFS】路径总和
题目地址：https://leetcode.cn/problems/path-sum/description/?envType=study-plan-v2&envId=top-interview-150
详见代码。
# 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 = rightclass Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False elif not root.left and not root.right and targetSum == root.val: return True else: return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right,targetSum-root.val)
9.10 【DFS】求根节点到叶节点数字之和
题目地址：https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/?envType=study-plan-v2&envId=top-interview-150
DFS，分别从根节点计算每一条路径的数字，然后求和，这里要注意判断条件，当一个节点没有左节点和右节点时，说明这条路径到底了，这是要把目前的数字加入到 a n s ans ans中。
# 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 = rightclass Solution: def sumNumbers(self, root: Optional[TreeNode]) -> int: ans = 0 def sub_sum(root,cur_num): nonlocal ans if not root.left and not root.right: ans += cur_num*10 + root.val return cur_num = cur_num*10 + root.val if root.left: sub_sum(root.left,cur_num) if root.right: sub_sum(root.right,cur_num) sub_sum(root,0) return ans
9.11 【BFS】【动态规划】二叉树中的最大路径和
题目地址：https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-interview-150
先找到每个节点下的最大路径和，再一步步从上往下遍历所有节点，如果遍历到某个节点的左子树或者右子树的最大和小于零，则这个子树可以不要，只需考虑另一个子树即可。
# 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 = rightclass Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: self.maxSum = -1001 def BFS(root): if not root: return 0 left_max = BFS(root.left) right_max = BFS(root.right) self.maxSum = max(self.maxSum, left_max + right_max + root.val) return max(0,max(left_max,right_max) + root.val) BFS(root) return self.maxSum
9.12 【BFS】二叉搜索树迭代器
题目地址：https://leetcode.cn/problems/binary-search-tree-iterator/description/?envType=study-plan-v2&envId=top-interview-150
先对二叉搜索树中的元素进行排序，然后按照题目要求构造函数即可。
# 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 = rightclass BSTIterator: def __init__(self, root: Optional[TreeNode]): self.root = root self.num = [] self.idx = 0 self.len = 0 def BFS(root): if not root: return self.num.append(root.val) self.len += 1 BFS(root.left) BFS(root.right) BFS(root) self.num.sort() def next(self) -> int: if self.idx bool: if self.idx
9.13 【BFS】完全二叉树的节点个数
题目地址：https://leetcode.cn/problems/count-complete-tree-nodes/description/?envType=study-plan-v2&envId=top-interview-150
详见代码。
# 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 = rightclass Solution: def countNodes(self, root: Optional[TreeNode]) -> int: self.ans = 0 def BFS(root): if not root: return self.ans += 1 BFS(root.left) BFS(root.right) BFS(root) return self.ans
9.14 【递归】二叉树的最近公共祖先
题目地址：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150
如果 p p p和 q q q位于二叉树的同一侧，那么最近公共祖先要么是 p p p要么是 q q q，如果位于二叉树的两侧，那么最近公共祖先则是两者最深的那个 r o o t root root。
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if not root or root == p or root == q: return root left = self.lowestCommonAncestor(root.left,p,q) right = self.lowestCommonAncestor(root.right,p,q) if not left: return right if not right: return left return root
10 二叉树层次遍历
10.1 【DFS】二叉树的右视图
题目地址：https://leetcode.cn/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-interview-150
深度优先遍历，每次都将二叉树每一层最右边的元素加入数组，同时设置 d e p t h depth depth来限制数组大小，保证数组中只有最右边的元素。
# 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 = rightclass Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: self.ans = [] def DFS(root, depth): if not root: return if len(self.ans)
10.2 【BFS】二叉树的层平均值
题目地址：https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150
详见代码。
# 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 = rightclass Solution: def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]: ans = [] node_list = [root] if not root: return ans while node_list: cur_val = [] nxt_list = [] for node in node_list: cur_val.append(node.val) if node.left: nxt_list.append(node.left) if node.right: nxt_list.append(node.right) ans.append(sum(cur_val)/len(cur_val)) node_list = nxt_list return ans
10.3 【BFS】二叉树的层序遍历
题目地址：https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=study-plan-v2&envId=top-interview-150
详见代码。
# 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 = rightclass Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: ans = [] cur_node = [root] if not root: return ans while cur_node: cur_val = [] nxt_node = [] for node in cur_node: cur_val.append(node.val) if node.left: nxt_node.append(node.left) if node.right: nxt_node.append(node.right) ans.append(cur_val) cur_node = nxt_node return ans
10.4 【BFS】二叉树的锯齿形层序遍历
题目地址：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/?envType=study-plan-v2&envId=top-interview-150
详见代码。
# 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 = rightclass Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: ans = [] cur_node = [root] flag = True if not root: return ans while cur_node: cur_val = [] nxt_node = [] for node in cur_node: cur_val.append(node.val) if node.left: nxt_node.append(node.left) if node.right: nxt_node.append(node.right) if flag: ans.append(cur_val) else: ans.append(cur_val[::-1]) flag = not flag cur_node = nxt_node return ans
11 二叉搜索树
11.1 【BFS】二叉搜索树的最小绝对差
题目地址：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/?envType=study-plan-v2&envId=top-interview-150
先遍历所有节点，然后排序，找出相邻元素差值最小的。
# 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 = rightclass Solution: def getMinimumDifference(self, root: Optional[TreeNode]) -> int: self.num = [] def BFS(root): if not root: return self.num.append(root.val) BFS(root.left) BFS(root.right) BFS(root) self.num.sort() ans = 100001 for i in range(len(self.num)-1): ans = min(ans,self.num[i+1]-self.num[i]) return ans
11.2 【BFS】二叉搜索树中第K小的元素
题目地址：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-interview-150
对于二叉搜索树而言，中序遍历就是其从小到大的排序结果，记录访问到的第 k k k个元素即可。
# 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 = rightclass Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: self.k = k self.ans = 0 def BFS(root): if not root: return BFS(root.left) self.k -= 1 if self.k == 0: self.ans = root.val return BFS(root.right) BFS(root) return self.ans
11.3 【BFS】【递归】验证二叉搜索树
题目地址：https://leetcode.cn/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-interview-150
递归实现，首先要明白二叉搜索树的判定条件，一是左子树
