最新消息: 电脑我帮您提供丰富的电脑知识,编程学习,软件下载,win7系统下载。

二叉树刷题指南

IT培训 admin 1浏览 0评论

二叉树刷题指南

文章目录

    • 一、完全二叉树的节点个数
    • 二、平衡二叉树
    • 三、二叉搜索树中的众数
    • 四、二叉搜索树中的插入操作
    • 五、修剪二叉搜索树

一、完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

示例1:

这是一棵完全二叉树:除最后一层外,其余层全部铺满;且最后一层向左停靠

  • 如果根节点的左子树深度等于右子树深度,则说明 左子树为满二叉树
  • 如果根节点的左子树深度大于右子树深度,则说明 右子树为满二叉树
  • 如果知道子树是满二叉树,那么就可以轻松得到该子树的节点数目:(1<<depth) - 1; depth为子树的深度;为了加快幂的运算速度,可以使用移位操作符
  • 接着我们只需要接着对另一子树递归即可
  • 时间复杂度为 O(logn∗logn)O(logn * logn)O(logn∗logn),空间复杂度为
    O(1)O(1)O(1)【不考虑递归调用栈】
class Solution:def countLevel(self, node):level = 0while node:level += 1node = node.leftreturn leveldef countNodes(self, root: Optional[TreeNode]) -> int:if not root: return 0left_level = self.countLevel(root.left)right_level = self.countLevel(root.right)# 左子树深度等于右子树深度, 左子树是满二叉树if left_level == right_level:# 满二叉树节点数和level的关系是2^level - 1, 即: 1 << left_level - 1, 为什么+1, 加上root这层return self.countNodes(root.right) + (1 << left_level - 1 + 1)else:return self.countNodes(root.left) + (1 << right_level - 1 + 1)

二、平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:true

示例 2:

输入:root = [1,2,2,3,3,null,null,4,4]
输出:false
class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:return self.dfs(root) != -1def dfs(self, node):# node is null, depth == 0if not node: return 0left = self.dfs(node.left)# if -1, 左子树存在高度差大于等于2的情况, 直接返回if left == -1: return -1right = self.dfs(node.right)# if -1, 右子树存在高度差大于等于2的情况, 直接返回if right == -1: return -1# 高度差小于2则取left tree和right tree的最大depth然后加1,算上本层。返回高度# 高度差大于等于2,则返回-1return max(left, right) + 1 if abs(left - right) < 2 else -1

三、二叉搜索树中的众数

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

如果树中有不止一个众数,可以按 任意顺序 返回。

假定 BST 满足如下定义:

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

示例 1:

输入:root = [1,null,2,2]
输出:[2]
class Solution:def findMode(self, root: Optional[TreeNode]) -> List[int]:self.max_rate, self.nums = 0, []self.cur_rate, self.cur_num = 0, Noneself.dfs(root)return self.numsdef dfs(self, node):if node:self.dfs(node.left)if self.cur_num == None or self.cur_num == node.val:self.cur_rate += 1else:self.cur_rate = 1self.cur_num = node.val# 注意这个判断要在前面, 不然下个判断的self.max_rate = self.cur_rate# 会造成两次判断都生效,或者用elif代替两次ifif self.cur_rate == self.max_rate:self.nums.append(node.val)if self.cur_rate > self.max_rate:self.max_rate = self.cur_rateself.nums = [node.val]self.dfs(node.right)

四、二叉搜索树中的插入操作

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

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1:

输入:root = [4,2,7,1,3], val = 5
输出:[4,2,7,1,3,5]

解释:另一个满足题目要求可以通过的树是:

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

五、修剪二叉搜索树

给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。

示例 1:

输入:root = [1,0,2], low = 1, high = 2
输出:[1,null,2]
class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root: returnif low > root.val:return self.trimBST(root.right, low, high)elif high < root.val:return self.trimBST(root.left, low, high)else:root.left = self.trimBST(root.left, low, high)root.right = self.trimBST(root.right, low, high)return root

二叉树刷题指南

文章目录

    • 一、完全二叉树的节点个数
    • 二、平衡二叉树
    • 三、二叉搜索树中的众数
    • 四、二叉搜索树中的插入操作
    • 五、修剪二叉搜索树

一、完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

示例1:

这是一棵完全二叉树:除最后一层外,其余层全部铺满;且最后一层向左停靠

  • 如果根节点的左子树深度等于右子树深度,则说明 左子树为满二叉树
  • 如果根节点的左子树深度大于右子树深度,则说明 右子树为满二叉树
  • 如果知道子树是满二叉树,那么就可以轻松得到该子树的节点数目:(1<<depth) - 1; depth为子树的深度;为了加快幂的运算速度,可以使用移位操作符
  • 接着我们只需要接着对另一子树递归即可
  • 时间复杂度为 O(logn∗logn)O(logn * logn)O(logn∗logn),空间复杂度为
    O(1)O(1)O(1)【不考虑递归调用栈】
class Solution:def countLevel(self, node):level = 0while node:level += 1node = node.leftreturn leveldef countNodes(self, root: Optional[TreeNode]) -> int:if not root: return 0left_level = self.countLevel(root.left)right_level = self.countLevel(root.right)# 左子树深度等于右子树深度, 左子树是满二叉树if left_level == right_level:# 满二叉树节点数和level的关系是2^level - 1, 即: 1 << left_level - 1, 为什么+1, 加上root这层return self.countNodes(root.right) + (1 << left_level - 1 + 1)else:return self.countNodes(root.left) + (1 << right_level - 1 + 1)

二、平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:true

示例 2:

输入:root = [1,2,2,3,3,null,null,4,4]
输出:false
class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:return self.dfs(root) != -1def dfs(self, node):# node is null, depth == 0if not node: return 0left = self.dfs(node.left)# if -1, 左子树存在高度差大于等于2的情况, 直接返回if left == -1: return -1right = self.dfs(node.right)# if -1, 右子树存在高度差大于等于2的情况, 直接返回if right == -1: return -1# 高度差小于2则取left tree和right tree的最大depth然后加1,算上本层。返回高度# 高度差大于等于2,则返回-1return max(left, right) + 1 if abs(left - right) < 2 else -1

三、二叉搜索树中的众数

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

如果树中有不止一个众数,可以按 任意顺序 返回。

假定 BST 满足如下定义:

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

示例 1:

输入:root = [1,null,2,2]
输出:[2]
class Solution:def findMode(self, root: Optional[TreeNode]) -> List[int]:self.max_rate, self.nums = 0, []self.cur_rate, self.cur_num = 0, Noneself.dfs(root)return self.numsdef dfs(self, node):if node:self.dfs(node.left)if self.cur_num == None or self.cur_num == node.val:self.cur_rate += 1else:self.cur_rate = 1self.cur_num = node.val# 注意这个判断要在前面, 不然下个判断的self.max_rate = self.cur_rate# 会造成两次判断都生效,或者用elif代替两次ifif self.cur_rate == self.max_rate:self.nums.append(node.val)if self.cur_rate > self.max_rate:self.max_rate = self.cur_rateself.nums = [node.val]self.dfs(node.right)

四、二叉搜索树中的插入操作

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

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1:

输入:root = [4,2,7,1,3], val = 5
输出:[4,2,7,1,3,5]

解释:另一个满足题目要求可以通过的树是:

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

五、修剪二叉搜索树

给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。

示例 1:

输入:root = [1,0,2], low = 1, high = 2
输出:[1,null,2]
class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root: returnif low > root.val:return self.trimBST(root.right, low, high)elif high < root.val:return self.trimBST(root.left, low, high)else:root.left = self.trimBST(root.left, low, high)root.right = self.trimBST(root.right, low, high)return root
11136

与本文相关的文章

发布评论

评论列表 (0)

  1. 暂无评论