二刷力扣--二叉树(3)

简介: 二刷力扣--二叉树(3)

106.从中序与后序遍历序列构造二叉树

给定两个整数数组 inorderpostorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树

手动构造的步骤:

后序确定根,中序分左右(子树)。

后序数组的最后一个元素(根)为切割点,先切中序数组,根据中序数组,反过来再切后序数组。一层一层切下去,每次后序数组最后一个元素就是节点元素。

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def traversal(inorder, postorder):
            if not postorder:
                return None
            
            # 根
            rootValue = postorder[-1]
            root = TreeNode(rootValue)
            # 叶子
            if len(postorder) == 1:
                return root
            
            #3. 找切割点
            inorder_index = inorder.index(rootValue)
            # 4. 切割 inorder 左、右
            leftInorder = inorder[:inorder_index] 
            rightInorder = inorder[inorder_index+1:]
            # 5. 切割 postoder 左、右
            postorder = postorder[:-1]
            leftPostorder = postorder[:len(leftInorder)]
            rightPostorder = postorder[len(leftInorder):]
            # 6. 递归处理
            root.left = traversal(leftInorder, leftPostorder)
            root.right = traversal(rightInorder, rightPostorder)

            return root

        if len(inorder) == 0 or len(postorder)==0:
            return None
        root = traversal(inorder, postorder)
        return root

654.最大二叉树

给定一个不重复的整数数组 nums最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点,其值为 nums 中的最大值。
  2. 递归地在最大值 左边子数组前缀上 构建左子树。
  3. 递归地在最大值 右边子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树

递归公式:

  1. 函数参数和返回值
    参数:待构建数组nums。
    返回值:通过nums构建的树的根节点root
  2. 终止条件
    nums为空,无法继续构建。
  3. 单层逻辑
    按照题目的描述。选出最大值,递归左右子树。
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def construct(nums):
            if not nums:
                return None
            max_value = max(nums)
            max_index = nums.index(max_value)
            root = TreeNode(max_value)
            
            left_nums = nums[:max_index]
            right_nums = nums[max_index+1:]

            root.left = construct(left_nums)
            root.right = construct(right_nums)

            return root
        return construct(nums)

(可以优化一下参数,每次不用传nums,而是传数组的左右边界)

617.合并二叉树

合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。

递归公式:

  1. 函数参数和返回值
    参数:两棵树的节点 t1, t2
    返回值:合并后的节点
  2. 终止条件:
    t1,t2其中一个为None,则直接返回另一个。
  3. 单层逻辑
    (t1,t2都不为None),两个节点值相加,并递归左右子树。
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        def helper(t1, t2):
            if t1 is None:
                return t2
            if t2 is None:
                return t1
            t1.val += t2.val
            t1.left = helper(t1.left, t2.left)
            t1.right = helper(t1.right, t2.right)
            return t1
        return helper(root1, root2)

700.二叉搜索树中的搜索

在二叉搜索树中找值为val的节点。

利用二叉树的性质(左<根<右)

递归公式:

  1. 参数:当前节点t。 返回值:节点或None
  2. 终止条件:t为空
  3. 单层逻辑:t.val == val,返回。t.val < val ,递归右子树。t.val > val ,递归左子树。
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        def helper(t):
            if t is None:
                return None
            if t.val == val:
                return t

            if t.val < val:
                return helper(t.right)
            else:
                return helper(t.left)
        
        return helper(root)

98.验证二叉搜索树

利用二叉树的性质(左<根<右),中序遍历的结果是一个递增的序列。

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:   
        def inorder(t):
            if t is None:
                return
            inorder(t.left)
            nums.append(t.val)
            inorder(t.right)

        nums = []
        inorder(root)
        return all(nums[i]<nums[i+1] for i in range(len(nums)-1))

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

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值

上面说过,二叉搜索树的中序遍历是一个递增 的,所以差值最小的两个节点一定是在中序遍历过程的相邻的两个节点。

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        def inorder(t):
            if t is None:
                return 
            
            inorder(t.left)
            nums.append(t.val)
            inorder(t.right)
        nums = []
        inorder(root)
        return min(nums[i+1] - nums[i]  for i in range(len(nums) - 1) )

501.二叉搜索树中的众数

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。

假定 BST 满足如下定义:

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树
class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        def inorder(t):
            if t is None:
                return 
            yield from inorder(t.left)
            yield t.val
            yield from inorder(t.right)
        nums = inorder(root)
        res = []
        max_times = 1
        cur_times = 1
        pre = -10**6
        for i, num in enumerate(nums):
            if num == pre:
                cur_times += 1
            else:
                pre = num 
                cur_times = 1
                
            if cur_times > max_times:
                max_times = cur_times
                res = [num]
            elif cur_times == max_times:
                res.append(num)

          return res

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

我们希望从下往上找两个节点的最近公共祖先,那么二叉树的后序遍历(左右中)就可以实现从下到上的顺序。

递归公式:

  1. 函数参数:当前节点root, 需要匹配的节点p, q
    返回值:如果当前节点是p/q祖先,则返回该节点。如果返回值为空,则表示没找到。
  2. 终止条件:
    当前节点为空或则和p/q匹配,则返回root。
  3. 单层逻辑
  1. 递归处理left和right。
    如果left和right都不为空,则root为最近公共祖先。
    如果left和right只有一个不为空,则返回不为空的那个。
    如果left和right都为空,则返回None。
class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root == q or root == p or root is None:
            return root

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

        if left  and right:
            return root

        if left is None and right:
            return right
        elif left  and right is None:
            return left
        else: 
            return None

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

这次找最近公共祖先可以从上到下找了。因为二叉搜索树满足(左<根<右),所以如果root的值在p,q之间,则说明root是p,q的公共祖先(并且是最近的)。

递归公式:

参数:当前节点t

返回值:当前节点t

终止条件:当前节点为None

单层逻辑:如果 t.val 比p,q的值都小,则说明该去右子树找;

如果 t.val 比p,q的值都大,则说明该去左子树找;

否则说明t就是p,q的分叉点,p,q一个在左,一个在右,t就是p,q的最近公共祖先,返回t。

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

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

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

在二叉树找到空节点插入新数据,不需要调整二叉树结构。

递归公式:

  1. 参数:当前节点root,待插入的值val
    返回值:root
  2. 终止条件:root 为None,创建值为val的节点node并返回node

单层逻辑:

if root.val > val, 递归左子树root.left = self.insertIntoBST(root.left, val)

if root.val < val, 递归右子树root.right = self.insertIntoBST(root.right, val)

返回root

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

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

删除二叉搜索树的节点,需要调整树的结构。

递归公式:

  1. 函数参数: 当前节点root, 待插入值key。
    返回值:返回删除后节点后的根节点。
  2. 终止条件: 当前节点为空,返回None
  3. 单层逻辑
    3.1 如果找到节点(if root.val == key),删除节点并调整结构。
    3.2 没找到节点,则递归查找。
if root.val > key:
  root.left = self.deleteNode(root.left, key)
if root.val < key:
  root.right = self.deleteNode(root.right, key)

3.3 返回root

其中3.1 删除节点可能遇到多种情况:

  1. 当前节点没有子节点了,直接删除,返回None
  2. 当前节点只有单侧节点(左/右),直接删除,返回左/右节点
  1. 左右节点都有,需要将左子树挂在右子树的最左下角,然后删除节点,返回右节点。
    (不需要显式删除节点)
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root is None:
            return None
        if root.val == key:
            if root.left is None and root.right is None:
                return None
            elif root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            else: # 左右都不为空时, 将 左子树 挂在右子树的最左下角
                cur = root.right
                while cur.left :
                    cur = cur.left
                cur.left = root.left  
                return  root.right
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        return root

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        def helper(t):
            # 终止条件
            if t is None:
                return None
            
            # 单层逻辑
            # 1.如果根<low,则(删除根和左孩子),处理右孩子并返回
            if t.val < low:
                right = helper(t.right)
                return right
            # 2.同理,如果根>high,则(删除根和右孩子),处理左孩子并返回
            if t.val > high:
                left = helper(t.left)
                return left
            # 3.如果结点的值位于区间 [low,high]
            # 递归处理左,右子树
            t.left = helper(t.left)
            t.right = helper(t.right)
            return t
        return helper(root)

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

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

数组构造二叉树,构成平衡树是自然而然的事情,因为大家默认都是从数组中间位置取值作为节点元素,一般不会随机取。所以想构成不平衡的二叉树是自找麻烦

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

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

给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

二叉搜索树满足左<根<右,所以为了知道比node值大的节点,需要按照 右,根,左的顺序访问(累加)。

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        pre = 0 # 非局部变量pre,记录上一个(修改过的)节点的值
        def traversal(cur):
            nonlocal pre
            if cur is None:
                return 
            # 右
            traversal(cur.right)
            # 根
            cur.val += pre
            pre = cur.val
            # 左
            traversal(cur.left)
        traversal(root)
        return root

相关文章
|
15天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
13 3
|
1月前
|
存储 算法 Python
二刷力扣--哈希表
二刷力扣--哈希表
|
1月前
二刷力扣--二叉树(2)
二刷力扣--二叉树(2)
|
1月前
二刷力扣--二叉树(1)基础、遍历
二刷力扣--二叉树(1)基础、遍历
|
1月前
|
存储 算法 Python
二刷力扣--栈和队列
二刷力扣--栈和队列
|
1月前
|
算法 索引 Python
二刷力扣--字符串
二刷力扣--字符串
|
1月前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
1月前
|
C++ Python
二刷力扣--数组
二刷力扣--数组
|
1月前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
|
1月前
|
算法 数据可视化 数据挖掘
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )