代码随想录27期|Day23|二叉树|669. 修剪二叉搜索树|108.将有序数组转换为二叉搜索树|538.把二叉搜索树转换为累加树
2023-12-23 17:48:03
图片来自代码随想录
669.?修剪二叉搜索树
本题一个初步的想法是,如果当前root的值在区间内,就进行子树的遍历;如果不满足,删除这个节点。
但是这样做会遇到问题。例如如下图示,如果在区间[1,3]内,如果直接在遍历到0的时候删除0节点,就会导致0的右子树(也在区间内)被删除。
所以需要在当前节点不满足的时候,进入到其左右子树再进行筛选,不能直接ruturn给上一层。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def trimBST(self, root, low, high):
"""
:type root: TreeNode
:type low: int
:type high: int
:rtype: TreeNode
"""
# 终止条件
if not root: # 遇到叶子节点返回
return
if root.val < low: # 当前节点小于low,转右子树去遍历
return self.trimBST(root.right, low, high)
if root.val > high: # 当前节点大于high,转左子树去遍历
return self.trimBST(root.left, low, high)
# 满足以上两个条件的子树被接入root的左右孩子
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low ,high)
return root
?108.?将有序数组转换为二叉搜索树
本题实际上是二叉树到数组的逆向过程。
基本思路是:先取数组的中间值作为root,然后构造左右子树。
循环不变量和区间的定义,这里采取的是双边闭区间。还要注意非偶数的重点一般取的是靠近left一侧的值。
递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
# 递归 闭区间
root = self.traversal(nums, 0, len(nums) - 1)
return root
def traversal(self, nums, left, right):
if left > right:
return None
mid = left + (right - left) // 2
node = TreeNode(nums[mid])
node.left = self.traversal(nums, left, mid - 1)
node.right = self.traversal(nums, mid + 1, right)
return node
精简版?
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not len(nums):
return
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[: mid])
root.right = self.sortedArrayToBST(nums[mid + 1 :])
return root
?538.?把二叉搜索树转换为累加树
使用双指针法,只不过是从树的最右端开始累加。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
self.pre = 0
self.traversal(root)
return root
def traversal(self, cur):
# 终止条件:走到最右端的空节点
if not cur:
return
# 中间处理:先右后左
self.traversal(cur.right)
# cur的值等于两个指针的和
cur.val += self.pre
self.pre = cur.val # 走一步之后需要把cur的值传给pre
# 再走左边
self.traversal(cur.left)
二叉树总结
可以参考星球上的大佬:代码随想录
?
第23天完结🎉
文章来源:https://blog.csdn.net/m0_57527624/article/details/135165259
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!