【leetcode刷题之路】面试经典150题（5）——二叉树+二叉树层次遍历+二叉搜索树

小明 2025-05-05 19:10:40 6

文章目录

      • 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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 = None
class 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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 = right
class 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
               

                递归实现，首先要明白二叉搜索树的判定条件，一是左子树
The End

标签：

微信