首页  思维导图  详情

二叉树题目整理

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