144. Binary Tree Preorder Traversal

  1. class Solution:
  2.     def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  3.         res = []
  4.         def dfs(root):
  5.             if not root:
  6.                 return              # 先序遍历:
  7.             res.append(root.val)    # root（处理当前节点核心逻辑）
  8.             dfs(root.left)          # left
  9.             dfs(root.right)         # right
  11.         dfs(root)
  12.         return res
  • 时间复杂度：二叉树 - 图1

  • 空间复杂度：二叉树 - 图2

    1. class Solution:
    2.   def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    3.       if not root:
    4.           return []
    6.       stack = [root]
    7.       res = []
    9.       while stack:
    10.           node = stack.pop()
    11.           res.append(node.val)
    12.           if node.right:                  # 先right后left，栈FILO
    13.               stack.append(node.right)
    14.           if node.left:
    15.               stack.append(node.left)
    17.       return res

  • 时间复杂度：二叉树 - 图3

  • 空间复杂度：二叉树 - 图4

    1. class Solution:
    2.   def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    3.       if not root:
    4.           return []
    6.       p = root
    7.       stack = []
    8.       res = []
    10.       while p or stack:
    11.           while p:                 # 一直向左走，边走边加入res
    12.               res.append(p.val)
    13.               stack.append(p)
    14.               p = p.left           # 先加入答案数组与栈后，再走向左孩子
    15.           p = stack.pop().right
    17.       return res

  • 时间复杂度：二叉树 - 图5

  • 空间复杂度：二叉树 - 图6

    可采用Morris遍历将空间复杂度降到二叉树 - 图7，暂不掌握。

94. Binary Tree Inorder Traversal

  1. class Solution:
  2.     def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  3.         def dfs(root):
  4.             if not root:
  5.                 return
  7.             dfs(root.left)
  8.             res.append(root.val)
  9.             dfs(root.right)
  11.         res = []
  12.         dfs(root)
  13.         return res
  • 时间复杂度：二叉树 - 图8，每个节点恰好被访问一次

  • 空间复杂度：二叉树 - 图9，取决于栈的深度，最坏情况下二叉树退化为链表

    1. class Solution:
    2.   def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    3.       if not root:
    4.           return []
    6.       res = []
    7.       stack = []
    8.       p = root
    10.       while p or stack:
    11.           while p:
    12.               stack.append(p)
    13.               p = p.left
    14.           node = stack.pop()
    15.           res.append(node.val)    # 出栈时才将节点值加入res
    16.           p = node.right
    18.       return res

  • 时间复杂度：二叉树 - 图10，每个节点恰好被访问一次

  • 空间复杂度：二叉树 - 图11，取决于栈的深度，最坏情况下二叉树退化为链表


145. Binary Tree Postorder Traversal

  1. class Solution:
  2.     def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  3.         def dfs(root):
  4.             if not root:
  5.                 return
  7.             dfs(root.left)
  8.             dfs(root.right)
  9.             res.append(root.val)
  11.         res = []
  12.         dfs(root)
  13.         return res
  • 时间复杂度：二叉树 - 图12
  • 空间复杂度：二叉树 - 图13

镜像先序遍历，再翻转输出。没有模拟真实的栈操作，是不太可取的做法。

  1. class Solution:
  2.     def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  3.         if not root:
  4.             return []
  6.         res = []
  7.         stack = [root]
  9.         while stack:
  10.             node = stack.pop()
  11.             res.append(node.val)
  12.             if node.left:
  13.                 stack.append(node.left)
  14.             if node.right:
  15.                 stack.append(node.right)
  17.         return res[::-1]
  1. class Solution:
  2.     def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  3.         if not root:
  4.             return []
  6.         res = []
  7.         stack = []
  8.         p = root
  10.         while p or stack:
  11.             while p:
  12.                 res.append(p.val)
  13.                 stack.append(p)
  14.                 p = p.right
  15.             p = stack.pop().left
  17.         return res[::-1]
  • 时间复杂度：二叉树 - 图14
  • 空间复杂度：二叉树 - 图15

利用栈的特性，增加一次入栈-出栈过程，通过flag位的设计使得两次出入栈的节点才能加入答案数组，以实现迭代版本的后序遍历。

  1. class Solution:
  2.     def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  3.         if not root:
  4.             return []
  6.         res = []
  7.         stack = [(0, root)]
  9.         while stack:
  10.             flag, node = stack.pop()
  11.             if flag == 1:                 # 第二次遍历，加入res
  12.                 res.append(node.val)
  13.             else:                         # 首次遍历，falg=1入栈，并将右-左孩子以flag=0入栈
  14.                 stack.append((1, node))
  15.                 if node.right:
  16.                     stack.append((0, node.right))
  17.                 if node.left:
  18.                     stack.append((0, node.left))
  20.         return res
  • 时间复杂度：二叉树 - 图16
  • 空间复杂度：二叉树 - 图17

102. Binary Tree Level Order Traversal

  1. from collections import deque
  3. class Solution:
  4.     def levelOrder(self, root: TreeNode) -> List[List[int]]:
  5.         if not root:
  6.             return []
  8.         res = []
  9.         queue = deque([root])
  11.         while queue:
  12.             layer, num_layer = [], len(queue)
  13.             for _ in range(num_layer):
  14.                 node = queue.popleft()
  15.                 layer.append(node.val)
  16.                 if node.left:
  17.                     queue.append(node.left)
  18.                 if node.right:
  19.                     queue.append(node.right)
  20.             res.append(layer)
  22.         return res
  • 时间复杂度：二叉树 - 图18
  • 空间复杂度：二叉树 - 图19

103. Binary Tree Zigzag Level Order Traversal

653. Two Sum IV - Input is a BST

Approach I
利用set记录，递归dfs实现，但没用到BST的特性。
同样可以使用bfs+queue实现，不再赘述。

  1. class Solution:
  3.     def __init__(self):
  4.         self.dic = set()
  6.     def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
  7.         if not root:
  8.             return False
  10.         if k - root.val in self.dic:
  11.             return True
  12.         self.dic.add(root.val)
  14.         return self.findTarget(root.left, k) or self.findTarget(root.right, k)
  • 时间复杂度：二叉树 - 图20
  • 空间复杂度：二叉树 - 图21

Approach II
再说吧
Approach II
再说啊

剑指 Offer 37. 序列化二叉树

  1. class Codec:
  3.     def serialize(self, root):
  4.         if not root:
  5.             return ''
  7.         data = []
  8.         queue = deque([root])
  10.         while queue:
  11.             node = queue.popleft()
  12.             if node:
  13.                 data.append(str(node.val))
  14.                 queue.append(node.left)
  15.                 queue.append(node.right)
  16.             else:
  17.                 data.append('null')
  19.         return ','.join(data)
  22.     def deserialize(self, data):
  23.         if data == '':
  24.             return
  26.         data = data.split(',')
  27.         root = TreeNode(int(data[0]))
  28.         index = 1
  29.         queue = deque([root])
  31.         while queue:
  32.             node = queue.popleft()
  33.             if data[index] != 'null':
  34.                 node.left = TreeNode(int(data[index]))
  35.                 queue.append(node.left)
  36.             index += 1
  38.             if data[index] != 'null':
  39.                 node.right = TreeNode(int(data[index]))
  40.                 queue.append(node.right)
  41.             index += 1
  43.         return root
  • 时间复杂度：二叉树 - 图22
  • 空间复杂度：二叉树 - 图23
  1. class Codec:
  3.     def serialize(self, root):
  4.         if not root:
  5.             return 'null'
  7.         return str(root.val) + ',' + self.serialize(root.left) \
  8.                              + ',' + self.serialize(root.right)
  11.     def deserialize(self, data):
  13.         def dfs(vals):
  14.             if (val := vals.popleft()) == 'null':
  15.                 return
  17.             node = TreeNode(int(val))
  18.             node.left = dfs(vals)
  19.             node.right = dfs(vals)
  21.             return node
  23.         vals = deque(data.split(','))
  24.         return dfs(vals)

剑指 Offer 55 - I. 二叉树的深度

  1. class Solution:
  2.     def maxDepth(self, root: TreeNode) -> int:
  3.         return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right)) \
  4.                if root else 0
  • 时间复杂度：二叉树 - 图24

  • 空间复杂度：二叉树 - 图25，取决于递归调用栈深度，最差情况退化为链表

    1. class Solution:
    2.   def maxDepth(self, root: TreeNode) -> int:
    3.       if not root:
    4.           return 0
    6.       queue = deque([root])
    7.       depth = 0
    9.       while queue:
    10.           depth += 1
    11.           num_layer = len(queue)
    12.           for _ in range(num_layer):
    13.               node = queue.popleft()
    14.               if node.left:
    15.                   queue.append(node.left)
    16.               if node.right:
    17.                   queue.append(node.right)
    19.       return depth

  • 时间复杂度：二叉树 - 图26

  • 空间复杂度：二叉树 - 图27，队列中最多存储二叉树 - 图28个节点

剑指 Offer 55 - II. 平衡二叉树

Approach I** 先序遍历 + 判断深度 （自顶向下）**

  1. class Solution:
  2.     def isBalanced(self, root: TreeNode) -> bool:
  3.         if not root:
  4.             return True
  6.         return abs(self.count_height(root.left) - self.count_height(root.right)) <= 1 \
  7.                and self.isBalanced(root.left) and self.isBalanced(root.right)
  9.     def count_height(self, root) -> int:
  10.         return 1 + max(self.count_height(root.left), self.count_height(root.right)) \
  11.                if root else 0
  • 时间复杂度：二叉树 - 图29
  • 空间复杂度：二叉树 - 图30

Approach I** 后序遍历 + 剪枝 （自底向上）**

  1. class Solution:
  2.     def isBalanced(self, root: TreeNode) -> bool:
  3.         def postorder_dfs(root):  # 若平衡，返回深度
  4.             if not root:          # 若不平衡，返回-1（剪枝）
  5.                 return 0
  7.             if (left := postorder_dfs(root.left)) == -1:
  8.                 return -1
  9.             if (right := postorder_dfs(root.right)) == -1:
  10.                 return -1
  12.             return 1 + max(left, right) if abs(left - right) <= 1 else -1
  14.         return postorder_dfs(root) != -1
  • 时间复杂度：二叉树 - 图31
  • 空间复杂度：二叉树 - 图32

543. Diameter of Binary Tree

**最大直径**不一定会经过root！故需要遍历所有节点判断。

  1. 使用类变量来记录&更新结果

  2. 同**平衡二叉树**的判断，使用后序遍历（自底向上）来减少复杂度

    • 若使用先序遍历，会造成大量重复计算

      class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
   self.diameter = 0

   def count_height(root):
       if not root:
           return 0

       L = count_height(root.left)
       R = count_height(root.right)
       self.diameter = max(self.diameter, L + R)

       return 1 + max(L, R)

   count_height(root)
   return self.diameter
  • 时间复杂度：二叉树 - 图33
  • 空间复杂度：二叉树 - 图34

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

对于**二叉搜索树**，恒有二叉树 - 图35

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val < root.val and q.val < root.val:  # p, q位于root左子树
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val and q.val > root.val:  # p, q位于root右子树
            return self.lowestCommonAncestor(root.right, p, q)
        return root                                # p, q位于root两侧 || p或q就是root
  • 时间复杂度：二叉树 - 图36
  • 空间复杂度：二叉树 - 图37
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val > q.val:           # 保证p.val < q.val
            return self.lowestCommonAncestor(root, q, p)

        while root:
            if q.val < root.val:    # p, q位于root左子树
                root = root.left
            elif root.val < p.val:  # p, q位于root右子树
                root = root.right
            else:                   # p, q位于root两侧 || p或q就是root
                return root
  • 时间复杂度：二叉树 - 图38
  • 空间复杂度：二叉树 - 图39

剑指 Offer 68 - II. 二叉树的最近公共祖先

class Solution:

    # 返回以root为根的二叉树中，p, q节点的最近公共祖先
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root == p or root == q:  # 若不成立，LCA必然不是root
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if not left and not right:              # root的左右子树都分别不'同时包含p,q'
            return
        if left and right:                      # p,q在root的异侧
            return root
        return left if left else right          # if left:
                                                # 1. p,q其中一个在root的左子树中
                                                # 2. p,q都在root的左子树中
  • 时间复杂度：二叉树 - 图40
  • 空间复杂度：二叉树 - 图41

剑指 Offer 07. 重建二叉树

使用dict来存储中序遍历的二叉树 - 图42到二叉树 - 图43的映射，故只适用于无重复节点值的二叉树。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        '''
        idx_pre: 前序遍历根节点的索引
        low: 中序遍历左边界
        high: 中序遍历右边界
        '''
        def build(idx_pre, low, high) -> TreeNode:
            if low > high:
                return

            val_root = preorder[idx_pre]
            idx_in = dic[val_root]

            root = TreeNode(val_root)
            root.left = build(idx_pre + 1, low, idx_in - 1)
            root.right = build(idx_pre + 1 + (idx_in - low), idx_in + 1, high)

            return root

        dic = dict()
        for index, num in enumerate(inorder):
            dic[num] = index
        return build(0, 0, len(inorder) - 1)
  • 时间复杂度：二叉树 - 图44
  • 空间复杂度：二叉树 - 图45

101. Symmetric Tree

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:

        # 判断L,R子树是否对称
        def dfs(L, R) -> bool:
            if not L and not R:    # L,R都为空 
                return True
            if not L or not R:     # L,R二者之一为空 || 存储的'val'不同
                return False
                                   # 递归比较
            return dfs(L.left, R.right) and dfs(L.right, R.left)

        return dfs(root.left, root.right)
  • 时间复杂度：二叉树 - 图46
  • 空间复杂度：二叉树 - 图47
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        queue = collections.deque([root.left, root.right])

        while queue:
            L, R = queue.popleft(), queue.popleft()
            if not L and not R:
                continue
            if not L or not R or L.val != R.val:
                return False
            queue += [L.left, R.right, L.right, R.left]

        return True
  • 时间复杂度：二叉树 - 图48
  • 空间复杂度：二叉树 - 图49

112. Path Sum

板子题

  1. root == None，恒为二叉树 - 图50
  2. 记得判断当前root是否为叶子节点：if not root.left and not root.right
    class Solution:
 # 遍历到root节点（还未考虑root.val），剩余需要填充的值是target
 def hasPathSum(self, root: Optional[TreeNode], target: int) -> bool:
     if not root:                            # 空节点
         return False
     if not root.left and not root.right:    # 叶子节点
         return target == root.val
     return self.hasPathSum(root.left, target - root.val) or \
            self.hasPathSum(root.right, target - root.val)
  • 时间复杂度：二叉树 - 图51
  • 空间复杂度：二叉树 - 图52
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], target: int) -> bool:
        if not root:
            return False

        queue = collections.deque([(root, root.val)])

        while queue:
            node, path_sum = queue.popleft()
            if not node.left and not node.right:
                if path_sum == target:
                    return True

            if node.left:
                queue.append((node.left, path_sum + node.left.val))
            if node.right:
                queue.append((node.right, path_sum + node.right.val))

        return False
  • 时间复杂度：二叉树 - 图53
  • 空间复杂度：二叉树 - 图54

113. Path Sum II

class Solution:
    def pathSum(self, root: Optional[TreeNode], target: int) -> List[List[int]]:

        def dfs(root, remain, path):
            if not root:
                return
            if not root.left and not root.right:
                if remain == root.val:
                    res.append(path + [root.val])
                return

            dfs(root.left, remain - root.val, path + [root.val])
            dfs(root.right, remain - root.val, path + [root.val])

        res = []
        dfs(root, target, [])
        return res

199. Binary Tree Right Side View

遍历顺序为二叉树 - 图55，额外使用变量**depth**来记录树的深度，可以构造出右视图的访问顺序。

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        def dfs(root, depth):
            if not root:
                return

            if depth == len(res):
                res.append(root.val)
            dfs(root.right, depth+1)
            dfs(root.left, depth+1)

        res = []
        dfs(root, 0)
        return res
  • 时间复杂度：二叉树 - 图56
  • 空间复杂度：二叉树 - 图57

利用队列进行广度优先搜索，只加入每一层的最后一个节点。

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        res = []
        depth = 0
        queue = collections.deque([root])
        while queue:
            num_layer = len(queue)
            for _ in range(num_layer):
                node = queue.popleft()
                if depth == len(res):
                    res.append(node.val)
                if node.right:
                    queue.append(node.right)
                if node.left:
                    queue.append(node.left)
            depth += 1
        return res
  • 时间复杂度：二叉树 - 图58
  • 空间复杂度：二叉树 - 图59

剑指 Offer 54. 二叉搜索树的第k大节点

使用类变量self.k和self.res来维护元素rank和节点值，逆向中序遍历，把逻辑处理全部写在对当前节点的操作上，故而简化了dfs()的参数。

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        def dfs(root):
            if not root:
                return
            dfs(root.right)
            ###
            self.k -= 1
            if self.k == 0:
                self.res = root.val
                return               # 剪枝
            ###
            dfs(root.left)

        self.k = k
        dfs(root)
        return self.res
  • 时间复杂度：二叉树 - 图60
  • 空间复杂度：二叉树 - 图61

129. Sum Root to Leaf Numbers

二叉树 - 图62

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:

        def dfs(root, prev_total):
            if not root:
                return 0

            total = prev_total * 10 + root.val
            if not root.left and not root.right:
                return total
            else:
                return dfs(root.left, total) + dfs(root.right, total)

        return dfs(root, 0)

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        res = 0
        queue = deque([(root, 0)])

        while queue:
            node, pre_total = queue.popleft()

            total = pre_total * 10 + node.val
            if not node.left and not node.right:
                res += total

            if node.left:
                queue.append((node.left, total))
            if node.right:
                queue.append((node.right, total))

        return res
  • 时间复杂度：二叉树 - 图63
  • 空间复杂度：二叉树 - 图64

98. Validate Binary Search Tree

226. Invert Binary Tree

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return

        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return

        queue = collections.deque([root])
        while queue:
            node = queue.popleft()
            node.left, node.right = node.right, node.left
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return root
  • 时间复杂度：二叉树 - 图65
  • 空间复杂度：二叉树 - 图66