IT小白

这个屌丝很懒，什么也没留下！

热门标签

树专题汇总（Leetcode+牛客）_leetcode tree专题

作者：IT小白 | 2024-07-05 01:47:43

踩

leetcode tree专题

leetcode题目整理——树
 二叉树总结篇
在这里插入图片描述

1、方法论

遍历：先序、后序、中序、层次
操作：构造、搜索、插入、删除

2、二叉树

① 普通遍历

Leetcode 144前序遍历145后序遍历 102层次遍历
 剑指 Offer 33. 二叉搜索树的后序遍历序列

使用子函数（左右子树对应的数组范围一直在变定义low、high）
定义p指针：从left开始，遍历左子树找出mid（mid=p），判断右子树（if(p!=right)）
检查左右子树

根据（前序中序）（中序后序）构造二叉树 105 106

思想：

建root节点
for循环找到分割数组的inorder的 index值
构造数组，构造树
int[ ] 新数组名 = Arrays.copyOfRange(旧数组名，下界，上界) 范围为：[下界，上界)，上界取不到,如果没有这个函数直接for循环出四个数组
不用新建函数加入left和right递归需要用到的参数，因为是直接新建了数组了，所有每一次递归 inorder[0]的值是不同的。

② 层次遍历

二叉树的层次遍历总结

Leetcode 144前序遍历145后序遍历 102层次遍历

使用一个queue、List<List< Integer>> res、count、List< Integer> tmp

二叉树的锯齿形层次遍历（按之字顺序打印二叉树） 103
二叉树的层序遍历（把二叉树打印成多行二维数组输出） 102

需要具体到每层，size for循环两个容器即可

二叉树的层次遍历 II（从底向上依次按行输出各层节点）107

把102的反转一下即可
问题：List<List< Integer>> data=new LinkedList<List< Integer>>();？？
add(0,tmp) addFirst为啥不对？？ reverse函数怎么说？？

找到树最左下角的节点的值 513

层次遍历最下层，先入右节点再入左节点，最后node的就是最下层最左边的节点
!que.isEmpty() Queue< TreeNode> que=new LinkedList<>();

二叉树的右视图 199

思想：用一个集合存放每一层的最右边的节点值
怎么具体到某一层的某个节点，用一个size for循环i=size-1的时候就好了
只要涉及到以行为单位的，用层次遍历和for循环

一棵树每层节点的平均数 637

跟上一题右视图处理方法一样，需要处理具体某一层的数了，就用一个size和一个for循环就好了

1 填充每个节点的下一个右侧节点指针 116

③ 递归

之前一直不理解树的前边的判断对于递归的作用，就只当成一个初始化的作用了，现在解释一下，以判断是不是same为例

    boolean issame(TreeNode root1,TreeNode root2){
        if(root1==null&&root2==null){
            return true;
        } //其实这是递归的出口，两个树同时遍历到为空的情况下没有返回false，
        //就可以返回true了
        if(root1==null||root2==null){
            return false;
        }//递归的出口2，两个树只有一个遍历到了空，就返回false了
        if(root1.val!=root2.val){//列举≠的
            return false;
        }
        return issame(root1.left,root2.right)&&issame(root1.right,root2.left);
1
2
3
4
5
6
7
8
9
10
11
12

相同的树100
另一个树的子树 572
树的子结构 26
镜像二叉树101

以上几个，利用一个private函数判断子树和root树的关系，利用子函数，有的是为了方便传入左右两个子树进行判断有的是为了能够进行迭代

翻转二叉树226

两句实现root+递归（利用tmp）

合并两个二叉树

root1（root2）==null
均不为null +合并
递归左右子树

④后序遍历

基于求树的高度（借用高度函数）

子树最大深度104 最小深度111

最大深度：root==null return 0 是出口，return max（left，right）+1求高度
最小深度要考虑某一个子树为空的状态，所以不能沿用直接min,判断函数变了：看两个子树是否都存在，存在直接min+1即可，有一个不存在就left+right+1

平衡二叉树110

递归——根节点的左右子树平衡否，用递归看各个子节点的子树平衡否。
用到求树的高度的函数，求左右子树高度
绝对值函数 Math.abs(left-right)

二叉树的直径 543

最长的路径并不一定过根节点
直径其实也是沿用了找到左右子树的最大高度，只不过这个root节点未必是根节点，所有要用一个sum=max(left+right，sum)来记录最长的那个
用两个函数，子函数是求左右子树高度的，然后顺便记录最长值，主函数是返回这个最长值的
路径比节点少1，直接路径=left+right

二叉树的最长同值路径 687

两个函数：子函数是经过root的同值路径的最大值，父函数 root可以不是根节点，靠调用父函数和子函数来实现

子函数，跟求直径完全一样，只不过加上了一个值相等的条件，把左边的最长路径，右边的最长路径找到
同理，使用sum记录所有的left+right

使用高度思想

求树高的的一般形式是这一类问题的基本形式，

先访问左子树拿到个值
在访问右子树拿到个值，
然后考虑当前节点返回一个新值。
求树高就是这个套路。稍微复杂一点的可能有一个全局值，在遍历过程中需要修改，比如543 求树中两节点距离的最大值。这种问题想明白后续遍历返回值是什么含义，可能的全局变量是什么含义这两个问题基本就结束了。

⑤ 路径和问题

自顶向下

就是从某一个节点(不一定是根节点)，从上向下寻找路径，到某一个节点(不一定是叶节点)结束，继续细分的话还可以分成一般路径与给定和的路径
路经总和的的三个题目112、113、437

根节点和叶子节点确定，求存在——左右为空且val=sum，true
根节点叶子节点确定，求路径——使用 data.tmp存序列，左右为空且val=sum tmp存入data，root=null 返回data
根节点叶子节点不确定，求数目

二叉树的所有路径
面试题 04.12. 求和路径
从叶结点开始的最小字符串
树的所有左叶子节点值的和 404
求根到叶子节点数字之和 129

非自顶向下：

就是从任意节点到任意节点的路径，不需要自顶向下
124. 二叉树中的最大路径和

⑥ 公共祖先总结

普通二叉树两节点的最近公共祖先 236
BST中两节点的最近公共祖先 235

公共祖先的情况可以分为：p是q的祖先，pq分别是左右子树，pq没有祖先（root==null）
BST中，看val值，都大于或都小于左右子树递归，一大一小返回root
普通二叉树，p和q为root返回，否则从左右子树中递归，若都有那么left和right分别为p、q则返回root，若只有left，返回left

3、二叉搜索树（BST）

验证树为BST 98

不只是要让左右节点满足要求，还要让左右子树的所有节点满足要求
long 引入：Long.MIN_VALUE,Long.MAX_VALUE

修剪BST 使之值位于给定最大值最小值之间 669

很巧妙，首先判断root的值跟（min，max）区间的关系，如果在区间之外，直接把左（右）子树砍掉，在区间里面再去分别修建左右子树
二叉搜索树的范围和 938
跟修建BST的思想很一致，就是考虑root的值，如果在区间里面的话，就把root.val和left和right的值加起来

把BST转化为累加树 538

sum是全局变量，记录累加和
sum+=root.val; root.val=sum;

二叉搜索树中第K小的元素230 第k大元素 J54

定义获得树节点总数的函数
某个子树的数目正好是k-1，root就是这个点
大于k-1 <k-1 分别讨论

BST中搜索插入删除节点700、701、450

搜索：看root的值是不是相等，不相等根据值去左右子树
插入：看root是不是空，空插入，不空根据值去左右子树
删除：根据root值和val的比较，不相等去左右子树删，想等再看root是否是叶子节点

有序【数组】【链表】转化为平衡的BST 108、109

数组：子函数的必要性，注意数组特性：下标求长度函数
链表：断链三指针(pre.next / slow / slow.next)

BST树中的两数之和为给定值 653

没办法用递归，因为两个节点有可能分别在左右子树上
把BST转换为一个递增序列，然后就是对序列的操作了
定义两个指针，从两边向中间靠，== k 是true， >k就j-- ，<k就i++
集合的定义List< Integer> data=new ArrayList< Integer>(); 数组的定义int data[] = null
从list中按照索引取数 data.get(i)，求list的长度 data.size()，像list中增加数 data.add(root.val);

BST最小绝对差 530
不同的二叉搜索树 95、96