跳至主要內容
968, 监控二叉树

一、题目描述

给定一个二叉树,我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象

计算监控树的所有节点所需的最小摄像头数量。

示例 1

输入: root = [0, 0, null, 0, 0]
输出: 1
解释: 如图所示,一台摄像头足以监控所有节点。

示例 2

输入: root = [0, 0, null, 0, null, 0, null, null, 0]
输出: 2
解释: 需要至少两个摄像头来监视树的所有节点。上图显示了摄像头放置的有效位置之一。


Mike大约 4 分钟greedyhardbinary treedepth first searchdynamic programming
572, 另一棵树的子树

一、题目描述

给你两棵二叉树rootsubRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在则返回true;否则返回false

二叉树tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。

示例 1

输入: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
输出: true


Mike大约 4 分钟binary treeeasybinary treedepth first searchstring matchinghash function
100, 相同的树

一、题目描述

给你两棵二叉树的根节点pq,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1

输入: p = [1, 2, 3], q = [1, 2, 3]
输出: true

示例 2

输入: p = [1, 2], q = [1, null, 2]
输出: false

示例 3

输入: p = [1, 2, 1], q = [1, 1, 2]
输出: false


Mike大约 2 分钟binary treeeasybinary treedepth first searchbreadth first search
109, 将有序列表转换为二叉搜索树

一、题目描述

给定一个单链表的头节点head,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差不超过1

示例 1

输入: head = [-10, -3, 0, 5, 9]
输出: [0, -3, 9, -10, null, 5]
解释: 一个可能的答案是[0,-3, 9,-10, null, 5],它表示所示的高度平衡的二叉搜索树。


Mike大约 3 分钟binary treemediumlinked listbinary treebinary search treedivide and conquer
108, 将有序数组转换为二叉搜索树

一、题目描述

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

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过1」的二叉树。

示例 1

输入: nums = [-10, -3, 0, 5, 9]
输出: [0, -3, 9, -10, null, 5]
解释: [0, -10, 5, null, -3, null, 9] 也将被视为正确答案:


Mike大约 3 分钟binary treeeasytreebinary treebinary search treearraydivide and conquer
669, 修剪二叉搜索树

一、题目描述

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

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

示例 1

输入: root = [1, 0, 2], low = 1, high = 2
输出: [1, null, 2]


Mike大约 2 分钟binary treemediumbinary treebinary search treedepth first search
450, 删除二叉搜索树中的节点

一、题目描述

给定一个二叉搜索树的根节点root和一个值key,删除二叉搜索树中的key对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

  1. 首先找到需要删除的节点;
  2. 如果找到了,删除它。

示例 1

输入: root = [5, 3, 6, 2, 4, null, 7], key = 3
输出: [5, 4, 6, 2, null, null, 7]
解释: 给定需要删除的节点值是3,所以我们首先找到3这个节点,然后删除它。


Mike大约 3 分钟binary treemediumbinary treebinary search tree
701, 二叉搜索树中的插入操作

一、题目描述

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

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

示例 1

输入: root = [4, 2, 7, 1, 3], val = 5
输出: [4, 2, 7, 1, 3, 5]
解释: 另一个满足题目要求可以通过的树是:


Mike大约 3 分钟binary treemediumbinary treebinary search tree
235, 二叉搜索树的最近公共祖先

一、题目描述

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

百度百科中最近公共祖先的定义为:"对于有根树T的两个结点pq,最近公共祖先表示为一个结点x,满足xpq的祖先且x的深度尽可能大(一个节点也可以是它自己的祖先)。"


Mike大约 4 分钟binary treemediumtreebinary treebinary search treedepth first search
236, 二叉树的最近公共祖先

一、题目描述

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

百度百科中关于公共祖先的定义为:"对于有根树T的两个节点pq,最近公共祖先表示为一个节点x,满足xpq的祖先且x的深度尽可能大(一个节点也可以是它自己的祖先)。"


Mike大约 3 分钟binary treemediumbinary treedepth first search
2
3
4
5