# 试题:树

LeetCode试题

# 难度:简单

#100 相同树

思路:使用递归,递归只判断当前节点情况,判断节点值为空情况,接着判断是否不等,如果相等则进行进一步左右子节点对比

#101 对称二叉树

思路:从根节点开始判断2个节点为空情况,以及不等情况,如果相等继续判断下一个左右子树的对称节点情况,思路与#100类似,差别在于,传入递归的子节点是对称位置的节点

#104 二叉树的最大深度

思路:如果当前节点为空则返回当前计数num,否则num++,再对左右节点进行计算最大深度,如果左子深度大于右子深度,则返回左子深度,依此类推,只要是有效层则num将会+1

#107 二叉树的层次遍历II

思路:层次遍历,使用队列把当前节点入队列,之后出队,再把左右子树入队,最后反转数组

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

思路;每次递归从数组中间开始创建节点,再递归生成左右节点,最后返回此节点作为上层递归节点的子节点,出口为当前数组无法再被分割

#110 平衡二叉树

思路:通过对每个节点判断子树高度差,递归节点直到null返回高度0,如果一个节点不满足则返回false,如果满足则返回当前节点最高高度,供上层递归比对高度差,直到根节点

#111 二叉树的最小深度

思路:对每个节点进行最小深度计算,如果当前计算的节点为null则返回递归出传入的深度,如果当前左右子节点都为null则说明是子叶节点,那么将深度+1之后再返回深度,如过最多一个子树为null则返回另一边的深度,如果都不为null则返回最小的那一边深度

#112 路径总和

思路:没递归一层sum减去当前节点值,再传入下一节点,如果当前为子叶节点并且sum为0则返回true,若sum不为0则此条路径无效返回false,这里要对根节点单独判断,如果根节点为null则返回false,递归思路同#111

#226 翻转二叉树

思路:除了递归出口的判断,也就是判断子叶和根为空的情况。还需要对左右子树分别递归,直到出口,最后再进行交换,也就是递归位置在交换之前,这样是自底向上翻转

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

思路:根据搜索树特性,对q、p与当前节点值比对,如果都比当前节点小那么继续左子树递归,如果都大继续右子树递归,否则返回当前节点,即最近的公共祖先

#257 二叉树的所有路径

思路:返回二叉树的所有到叶子节点的路径,那么递归到叶子节点时就可以把一路拼接的字符串push到保存的数组中,最后再返回,当不是叶子节点时,继续拼接路径,根据子树情况进行递归选择

#404 左叶子之和

思路:在非子叶节点判断其左子叶节点是否存在,如果存在则返回左子叶节点的值和其又节点递归值的和,如果当前节点为null则返回0

#501 二叉搜索树中的众数

思路:使用中序遍历,为有序数组,记录当前和上一个值,使用者2个值对一个数字进行计数,并且更新最大计数值如果当前最大计数值与之前记录的最大计数值相同,则数组添加新众数,否则覆盖原来众数列表,注意变量作用域

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

思路:同#501,也要使用公共变量,使用中序遍历,获取前后差值的最小作为最终返回值

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

思路:同之前的二叉搜索树,但是这里使用反向中序遍历,即从大到小遍历,也就是右中左遍历,把之前遍历的树都push到数组中,然后对每个当前节点值使用累加计算和

#543 二叉树的直径

思路:就是计算左右子树的最高高度和,当遇到叶子节点则返回0 ,每次递归返回的是高度,而直径使用公共变量来保存,每次计算对比最大直径并且替换

#559 N叉树的最大深度

思路:同二叉树最大深度,这里需要遍历所有子节点,计算其中最大的深度作为当前节点最大深度,然后返回深度+1

#563 二叉树的坡度

思路:使用公共变量记录所有节点的坡度和,递归返回的是此节点的所有节点和包括自身节点值,上层节点对比左右子树的和差的绝对值作为当前节点的坡度累计到sum中

#572 另一个树的子树

思路:单独写一个判断二叉树相等的函数,主函数中判断当前节点值与对比树的根节点值是否相同,相同则判断2个树是否相同。有一个特殊情况,有可能节点的值是重复的,所以也要或上,左右子树与对比树的比对,只要满足一个匹配成即可。如果当前节点与对比根节点不同则递归左右节点,注意点,必须是子树匹配

#589 N叉树的前序遍历

思路:思路同二叉树,把当前值push进遍历数组,对children进行循环递归

#590 N叉树的后序遍历

思路:同二叉树,对children进行循环递归,再把当前值push进遍历数组

#606 根据二叉树创建字符串

思路:如果当前是叶子节点则直接返回当前节点值,如果当前右子树为null,则返回 当前节点值(左节点值),其他情况都存在则正常返回 当前节点值(左节点值)(右节点值)

#617 合并二叉树

思路:判断当前2节点是否都存在,都存在则合并值,并且继续递归合并左右子树,否则返回左或者右存在的子树,注意默认返回节点

#637 二叉树的层平均值

思路:层次遍历,记录当前层的平均值,层次遍历使用队列来保存当前层节点

#653 两数之和IV-输入BST

思路:使用set存储当前遍历过的所有节点值,当目标值减去当前值的结果存在于set中,则说明存在2个节点值之和为k

#669 修剪二叉搜索树

思路:当前值小于下限则直接返回右子树,当前值大于上限则返回左子树,否则正常递归左右子树,并重新赋值,最后返回修剪的节点

#671 二叉树中第二小的节点

思路:由于最小的节点为根节点,所以需要找出左右子树中最小的节点值,且不等于根节点,否则返回-1

#687 最长同值路径

思路:递归,对比左右子树值是否与当前值相同,相同则路径加1,不同则清0,返回左右子树最长相同路径

#700 二叉搜索树中的搜索

思路:对搜索树进行中序遍历,如果当前值等于给定值则返回当前节点,否则返回null。也可以根据搜索树的特性,对值进行比对并根据情况进行左右递归子树

#783 二叉搜索树节点最小距离

思路;同#530,使用公共变量来存储当前最小值,中序遍历对比相邻2个节点差值与当前最小值,并且更新min的取值,当全部遍历完,则返回min

#872 叶子相似的树

思路:对2树分别进行DFS,并返回每次递归由子叶节点组成的字符串,对比2个字符串是否相等来判断是否树相似

#897 递增顺序查找树

思路:使用中序遍历,按遍历顺序生成只有右子树的二叉树,或者通过变换节点位置,比如把左子树变为父子树并且当前节点变为父子树的右子树再把当前节点左子树赋null,这里需要一个head节点来保存第一次获取到的节点值,作为最终返回的根节点

#938 二叉搜索树的范围和

思路:当当前节点值小于下限时,返回右子树递归结果,当当前节点值大于上限时,返回左子树递归结果,其他情况返回左右子树递归结果与当前节点值的和

#965 单值二叉树

思路:当左右子树都为空则返回true,否则返回当前值与存在的左右子树值是否相等以及对存在子树进一步递归

#993 二叉树的堂兄弟节点

思路:使用层次遍历,判断当前队列节点的左右子树情况,并使用变量来标记。或者通过计算每个节点的深度,最后对比给定2个节点值对应的深度是否相同

#1022 从根到叶的二进制数之和

思路:每递归一层则使用字符串拼接当前值,再传给子树继续拼接,直到叶子节点额外使用分隔符拼接,最后返回所有拼接而成的字符串,使用splice分割成数组,最后循环解析二进制数并求和

上次更新: 2020-8-22 21:22:03