分门别类刷算法，坚持，进步！
刷题路线参考：https://github.com/youngyangyang04/leetcode-master
大家好，我是拿输出博客来督促自己刷题的老三，这一节我们来刷二叉树，二叉树相关题目在面试里非常高频，而且在力扣里数量很多，足足有几百道，不要慌，我们一步步来。我的文章很长，你们 收藏一下。
二叉树基础
二叉树是一种比较常见的数据结构，在开始刷二叉树之前，先简单了解一下一些二叉树的基础知识。更详细的数据结构知识建议学习《数据结构与算法》。
什么是二叉树
二叉树是每个节点至多有两棵子树的树。
二叉树主要的两种形式：满二叉树和完全二叉树。
-
满?叉树：如果?棵?叉树只有度为0的结点和度为2的结点，并且度为0的结点在同?层上，则这棵?
叉树为满?叉树。一棵深度为k的满二叉树节点个数为2k -1。
-
完全?叉树：至多只有最下面的两层结点的度数可以小于 2, 并且最下一层上的结点都集中在该层最左边的若干位置上， 则此二叉树称为完全二叉树。
我们可以看出满二叉树是完全二叉树， 但完全二叉树不一定是满二叉树。
?叉搜索树
?叉搜索树，也可以叫二叉查找树、二叉排序树，是一种有序的二叉树。它遵循着左小右大的规则：
- 若它的左?树不空，则左?树上所有结点的值均?于它的根结点的值；
- 若它的右?树不空，则右?树上所有结点的值均?于它的根结点的值；
- 它的左、右?树也分别为?叉搜索树
二叉树存储结构
和线性表类似，二叉树的存储结构也可采用顺序存储和链式存储两种方式。
顺序存储是将二叉树所有元素编号，存入到一维数组的对应位置，比较适合存储满二叉树。
由于采用顺序存储结构存储一般二叉树造成大量存储空间的浪费， 因此， 一般二叉树的存储结构更多地采用链式的方式。
二叉树节点
我们在上面已经看了二叉树的链式存储，注意看，一个个节点是由三部分组成的，左孩子、数据、右孩子。
我们来定义一下二叉树的节点节点：
/**
* @Author: 三分恶
* @Date: 2021/6/8
* @Description:
**/
public class TreeNode {
int val; //值
TreeNode left; //左子树
TreeNode right; //右子树
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
二叉树遍历方式
?叉树主要有两种遍历?式：
-
深度优先遍历：先往深?，遇到叶?节点再往回?。
-
?度优先遍历：?层?层的去遍历。
那么从深度优先遍历和?度优先遍历进?步拓展，才有如下遍历?式：
-
深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
-
?度优先遍历
- 层次遍历（迭代法）
我们耳熟能详的就是根、左、右三种遍历，所谓根、左、右指的就是根节点的次序：
- 前序遍历：根左右
- 中序遍历：左根右
- 后序遍历：左右根
还有一种更利于记忆的叫法：先根遍历、中根遍历、后根遍历，这种说法就更一目了然了。
我们来看一个图例：
具体的算法实现主要有两种方式：
- 递归：树本身就是一种带着递归性质的数据结构，使用递归来实现深度优先遍历还是非常方便的。
- 迭代：迭代需要借助其它的数据结构，例如栈来实现。
好了，我们已经了解了二叉树的一些基础知识，接下来，面对LeetCode的疯狂打击吧！
深度优先遍历基础
递归基础
二叉树是一种天然递归的数据结构，我们先简单碰一碰递归。
递归有三大要素：
-
递归函数的参数和返回值
确定哪些参数是递归的过程中需要处理的，那么就在递归函数?加上这个参数， 并且还要明确每次递归的返回值是什么进?确定递归函数的返回类型。
-
终?条件：
递归需要注意终止条件，终?条件或者终?条件写的不对，操作系统的内存栈就会溢出。
-
单层递归的逻辑
确定单层递归的逻辑，在单层里会重复调用自己来实现递归的过程。
好了，那么我们开始吧！
LeetCode144. 二叉树的前序遍历
那么先从二叉树的前序遍历开始吧。
? 题目：LeetCode144. 二叉树的前序遍历 (https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)
? 难度：简单
📕 描述：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
💡 思路：
递归法前序遍历
我们前面看了递归三要素，接下来我们开始用递归法来进行二叉树的前序遍历：
- 确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数?需要传?List用来存放节点的数值；要传入节点的值，自然也需要节点，那么递归函数的参数就确定了；因为节点数值已经存在List里了，所以递归函数返回类型是void，代码如下：
void preOrderRecu(TreeNode root, List<Integer> nodes)
- 确定终?条件：递归结束也很简单，如果当前遍历的这个节点是空，就直接return，代码如下：
//递归结束条件
if (root == null) {
return;
}
- 确定单层递归的逻辑：前序遍历是根左右的顺序，所以在单层递归的逻辑里，先取根节点的值，再递归左子树和右子树，代码如下：
//添加根节点
nodes.add(root.val);
//递归左子树
preOrderRecu(root.left, nodes);
//递归右子树
preOrderRecu(root.right, nodes);
我们看一下二叉树前序遍历的完整代码：
/**
* 二叉树前序遍历
*
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<>(16);
preOrderRecu(root, nodes);
return nodes;
}
/**
* 二叉树递归前序遍历
*
* @param root
* @param nodes
*/
void preOrderRecu(TreeNode root, List<Integer> nodes) {
//递归结束条件
if (root == null) {
return;
}
//添加根节点
nodes.add(root.val);
//递归左子树
preOrderRecu(root.left, nodes);
//递归右子树
preOrderRecu(root.right, nodes);
}
单元测试：
@Test
public void preorderTraversal() {
LeetCode144 l = new LeetCode144();
//构造二叉树
TreeNode root = new TreeNode(1);
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(3);
root.left = node1;
node1.right = node2;
//二叉树先序遍历
List<Integer> nodes = l.preorderTraversal(root);
nodes.stream().forEach(n -> {
System.out.print(n);
});
}
复杂度：
- 🚗 时间复杂度：O(n)，其中 n 是二叉树的节点数。
递归法会者不难，难者不会。只要能理解，这个是不是很轻松？😂
我们接下来，搞一下稍微麻烦一点的迭代法。
迭代法前序遍历
迭代法的原理是引入新的数据结构，用来存储遍历的节点。
递归的过程是不断往左边走，当递归终止的时候，就添加节点。现在使用迭代，我们需要自己来用一个数据结构存储节点。
那么用什么数据结构比较合适呢？我们自然而然地想到——栈。
迭代法的核心是： 借助栈结构，模拟递归的过程，需要注意何时出栈入栈，何时访问结点。
前序遍历地顺序是根左右，先把根和左子树入栈，再将栈中的元素慢慢出栈，如果右子树不为空，就把右子树入栈。
ps：注意啊，我们的写法将存储元素进列表放在了栈操作前面，栈的作用主要用来找右子树。
迭代和递归究其本质是一样的东西，不过递归里这个栈由虚拟机帮我们隐式地管理了。
/**
* 二叉树前序遍历-迭代法
*
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<>(16);
if (root == null) {
return nodes;
}
//使用链表作为栈
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while(root!=null || !stack.isEmpty()){
while(root!=null){
//根
nodes.add(root.val);
stack.push(root);
//左
root=root.left;
}
//出栈
root=stack.pop();
//右
root=root.right;
}
return nodes;
}
- 🚗时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
LeetCode94. 二叉树的中序遍历
? 题目：LeetCode94. 二叉树的中序遍历 (https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)
? 难度：简单
📕 描述：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
- 递归法中序遍历
我们在前面已经用递归法进行了二叉树大的前序遍历，中序遍历类似，只是把根节点的次序放到中间而已。
/**
* 中序遍历-递归
*
* @param root
* @param nodes
*/
void inOrderRecu(TreeNode root, List<Integer> nodes) {
if (root == null) {
return;
}
//递归左子树
inOrderRecu(root.left, nodes);
//根节点
nodes.add(root.val);
//递归右子树
inOrderRecu(root.right, nodes);
}
-
迭代法中序遍历
迭代法中序，也是使用栈来保存节点。
迭代法中序遍历和前序遍历类似，只是我们访问节点的时机不同而已：
- 前序遍历需要每次向左走之前就访问根结点
- 而中序遍历先压栈，在出栈的时候才访问
将节点的所有左孩子压入栈中，然后出栈，出栈的时候将节点的值放入List，如果节点右孩子不为空，就处理右孩子。
/**
* 中序遍历-迭代
*
* @param root
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<>(16);
if (root == null) {
return nodes;
}
//使用链表作为栈
Deque<TreeNode> stack = new LinkedList<TreeNode>();
while (root != null || !stack.isEmpty()) {
//遍历左子树
while (root != null) {
stack.push(root);
root = root.left;
}
//取出栈中的节点
root = stack.pop();
//添加取出的节点
nodes.add(root.val);
//右子树
root = root.right;
}
return nodes;
}
LeetCode145. 二叉树的后序遍历
? 题目：145. 二叉树的后序遍历 (https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)
? 难度：简单
📕 描述：给定一个二叉树，返回它的 后序 遍历。
- 递归法后序遍历
递归法，只要理解了可以说so easy了！
/**
* 二叉树后序遍历-递归
*
* @param nodes
* @param root
*/
void postorderRecu(List<Integer> nodes, TreeNode root) {
if (root == null) {
return;
}
//递归左子树
postorderRecu(nodes, root.left);
//递归右子树
postorderRecu(nodes, root.right);
//根子树
nodes.add(root.val);
}
- 迭代法后序遍历
递归法后序遍历，可以用一个取巧的办法，套用一下前序遍历，前序遍历是根左右，后序遍历是左右根，我们只需要将前序遍历的结果反转一下，就是根左右。
如果使用Java实现，可以在链表上做文章，将尾插改成头插也是一样的效果。
/**
* 二叉树后序遍历-迭代
*
* @param root
* @return
*/
public List<Integer> postorderTraversal(TreeNode root) {
//使用链表作为栈
Deque<TreeNode> stack = new LinkedList<TreeNode>();
//节点
LinkedList<Integer> nodes = new LinkedList<Integer>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
//头插法插入节点
nodes.addFirst(root.val);
//根节点入栈
stack.push(root);
//左子树
root = root.left;
}
//节点出栈
root = stack.pop();
//右子树
root = root.right;
}
return nodes;
}
当然，这是一种取巧的做法，你说这不是真正的迭代法后序遍历，要真正的后序迭代二叉树，也不复杂，
重点在于：
- 如果右子树为空或者已经访问过了才访问根结点
- 否则，需要将该结点再次压回栈中，去访问其右子树
/**
* 二叉树后序遍历-迭代-常规
*
* @param root
* @return
*/
public List<Integer> postorderTraversal1(TreeNode root) {
//使用链表作为栈
Deque<TreeNode> stack = new LinkedList<TreeNode>();
//节点值存储
List<Integer> nodes = new ArrayList<>(16);
//用于记录前一个节点
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
//根节点入栈
stack.push(root);
//左子树
root = root.left;
}
//节点出栈
root = stack.pop();
//判断节点右子树是否为空或已经访问过
if (root.right == null || root.right == pre) {
//添加节点
nodes.add(root.val);
//更新访问过的节点
pre = root;
//使得下一次循环直接出栈下一个
root = null;
} else {
//再次入栈
stack.push(root);
//访问右子树
root = root.right;
}
}
return nodes;
}
广度优先遍历基础
LeetCode102. 二叉树的层序遍历
? 题目：102. 二叉树的层序遍历(https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
? 难度：中等
📕 描述：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
我们在前面已经使用迭代法完成了二叉树的深度优先遍历，现在我们来磕一下广度优先遍历。
在迭代法深度优先遍历里，我们用了栈这种数据结构来存储节点，那么层序遍历这种一层一层遍历的逻辑，适合什么数据结构呢？
答案是队列。
那么层序遍历的思路是什么呢？
使用队列，把每一层的节点存储进去，一层存储结束之后，我们把队列中的节点再取出来，左右孩子节点不为空，我们就把左右孩子节点放进去。
/**
* 二叉树层序遍历
*
* @param root
* @return
*/
public List<List<Integer>> levelOrder(TreeNode root) {
//结果集合
List<List<Integer>> result = new ArrayList<>(16);
if (root == null) {
return result;
}
//保存节点的队列
Queue<TreeNode> queue = new LinkedList<>();
//加入根节点
queue.offer(root);
while (!queue.isEmpty()) {
//存放每一层节点的集合
List<Integer> level = new ArrayList<>(8);
//这里每层队列的size要先取好，因为队列是不断变化的
int queueSize = queue.size();
//遍历队列
for (int i = 1; i <= queueSize; i++) {
//取出队列的节点
TreeNode node = queue.poll();
//每层集合中加入节点
level.add(node.val);
//如果当前节点左孩子不为空，左孩子入队
if (node.left != null) {
queue.offer(node.left);
}
//如果右孩子不为空，右孩子入队
if (node.right != null) {
queue.offer(node.right);
}
}
//结果结合加入每一层结果集合
result.add(level);
}
return result;
}
- 🚗时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。
好了，二叉树的深度优先遍历和广度优先遍历的基础已经完成了，接下来，我们看一看，在这两种遍历的基础上衍生出的各种变化吧！
广度优先遍历基础-变式
我们首先来看一下在层序遍历的基础上，稍微有一些变化的题目。
剑指 Offer 32 - I. 从上到下打印二叉树
? 题目：剑指 Offer 32 - I. 从上到下打印二叉树 (https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/)
? 难度：中等
📕 描述：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
💡思路：
这道题可以说变化非常小了。
该咋做？
就这么做！
/**
* 从上到下打印二叉树
*
* @param root
* @return
*/
public int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
List<Integer> nodes=new ArrayList<>(64);
//队列
Deque<TreeNode> queue = new LinkedList<>();
//根节点
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
nodes.add(node.val);
//左孩子入队
if (node.left != null) {
queue.offer(node.left);
}
//右孩子入队
if (node.right != null) {
queue.offer(node.right);
}
}
//结果数组
int[] result = new int[nodes.size()];
for (int i = 0; i < nodes.size(); i++) {
result[i] = nodes.get(i);
}
return result;
}
代码没改几行，往里面套就完了。
剑指 Offer 32 - III. 从上到下打印二叉树 III
? 题目：剑指 Offer 32 - III. 从上到下打印二叉树 III(https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/)
? 难度：中等
📕 描述：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
💡思路：
这个题目的变化是奇数层要从左往右打印，偶数层要从右往左打印。
所以我们需要一个变量来记录层级。
那什么数据结构既能从左往右插数据，又能从右往左插数据呢？
我们想到了双向链表。
/**
* 剑指 Offer 32 - III. 从上到下打印二叉树 III
*
* @param root
* @return
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>(32);
if (root == null) {
return result;
}
//队列
Deque<TreeNode> queue = new LinkedList<>();
//根节点
queue.offer(root);
//记录层级
int levelCount = 1;
while (!queue.isEmpty()) {
//当前队列size
int queueSize = queue.size();
//使用双向链表存储每层节点
LinkedList<Integer> level = new LinkedList<>();
for (int i = 1; i <= queueSize; i++) {
//取节点
TreeNode node = queue.poll();
//判断层级
//奇数，尾插
if (levelCount % 2 == 1) {
level.addLast(node.val);
}
//偶数，头插
if (levelCount % 2 == 0) {
level.addFirst(node.val);
}
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
//右孩子
if (node.right != null) {
queue.offer(node.right);
}
}
//添加每层节点
result.add(level);
//层级增加
levelCount++;
}
return result;
}
LeetCode107. 二叉树的层序遍历 II
? 题目：107. 二叉树的层序遍历 II (https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/)
? 难度：中等
📕 描述：给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
💡思路：
还记得我们后序遍历二叉树的取巧做法吗？这不就是一回事吗，层序遍历，反转List，或者用链表头插每一层的集合。
/**
* 二叉树的层序遍历 II
*
* @param root
* @return
*/
public List<List<Integer>> levelOrderBottom(TreeNode root) {
//使用链表存储结果，使用头插法添加元素
LinkedList<List<Integer>> result = new LinkedList<>();
if (root == null) {
return result;
}
//队列
Deque<TreeNode> queue = new LinkedList<>();
//插入根节点
queue.offer(root);
while (!queue.isEmpty()) {
//存放每一层节点的集合
List<Integer> level = new ArrayList<>(8);
//当前队列size，需要取好，因为队列在不断变化
int currentQueueSize = queue.size();
//遍历队列
for (int i = 1; i <= currentQueueSize; i++) {
TreeNode node = queue.poll();
//每一层集合添加值
level.add(node.val);
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
//右孩子
if (node.right != null) {
queue.offer(node.right);
}
}
//头插法插入每一层节点集合
result.addFirst(level);
}
return result;
}
LeetCode199. 二叉树的右视图
? 题目：199. 二叉树的右视图 (https://leetcode-cn.com/problems/binary-tree-right-side-view/)
? 难度：中等
📕 描述：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
💡思路：
这个也很简单对不对？
我们只需要判断一下，节点是不是每层最后一个元素，是就加入集合。
怎么判断？记得我们维护的有一个每层的元素个数变量吗？拿这个判断。
/**
* 二叉树的右视图
*
* @param root
* @return
*/
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>(16);
if (root == null) {
return result;
}
//队列
Deque<TreeNode> queue = new LinkedList<>();
//根节点入队
queue.offer(root);
while (!queue.isEmpty()) {
//维护队列当前size
int queueCurrentSize = queue.size();
for (int i = 1; i <= queueCurrentSize; i++) {
//取出当前遍历的节点
TreeNode node = queue.poll();
//判断是否最右一个
if (i == queueCurrentSize) {
//结果集合添加节点值
result.add(node.val);
}
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
//右孩子
if (node.right != null) {
queue.offer(node.right);
}
}
}
return result;
}
LeetCode637. 二叉树的层平均值
? 题目：637. 二叉树的层平均值(https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/)
? 难度：简单
📕 描述：给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
每层求和，再除个节点个数，取个均值。
/**
* 637. 二叉树的层平均值
*
* @param root
* @return
*/
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
if (root == null) {
return result;
}
//队列
Deque<TreeNode> queue = new LinkedList<>();
//根节点
queue.offer(root);
while (!queue.isEmpty()) {
int currentQueueSize = queue.size();
//每一层值的总和
double levelSum = 0;
for (int i = 1; i <= currentQueueSize; i++) {
TreeNode node = queue.poll();
//累加
levelSum += node.val;
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
//平均值
double avg = levelSum / currentQueueSize;
//结果集合添加每层平均值
result.add(avg);
}
return result;
}
LeetCode429. N 叉树的层序遍历
? 题目：429. N 叉树的层序遍历(https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/)
? 难度：中等
📕 描述：给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
和二叉树的层序遍历类似，不多树变成了N叉树，思路差不多，只不过左右子节点的入队，变成了子节点集合节点的入队。
/**
* 429. N 叉树的层序遍历
*
* @param root
* @return
*/
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>(16);
if (root == null) {
return result;
}
//队列
Deque<Node> queue = new LinkedList<>();
//根节点
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>(8);
int currentQueueSize = queue.size();
for (int i = 1; i <= currentQueueSize; i++) {
Node node = queue.poll();
level.add(node.val);
//判断子节点是否为空，添加子节点
if (!node.children.isEmpty()) {
queue.addAll(node.children);
}
}
//添加每层节点
result.add(level);
}
return result;
}
LeetCode515. 在每个树行中找最大值
? 题目：515. 在每个树行中找最大值 (https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/)
? 难度：中等
📕 描述：您需要在二叉树的每一行中找到最大的值。
💡思路：
定义一个变量，来表示每层最大数。
/**
* 515. 在每个树行中找最大值
*
* @param root
* @return
*/
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<>(16);
if (root == null) {
return result;
}
//队列
Deque<TreeNode> queue = new LinkedList<>();
//根节点
queue.offer(root);
while (!queue.isEmpty()) {
int queueSize = queue.size();
//最大值
Integer max = Integer.MIN_VALUE;
//遍历一层
for (int i = 1; i <= queueSize; i++) {
//取节点
TreeNode node = queue.poll();
if (node.val > max) {
max = node.val;
}
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(max);
}
return result;
}
LeetCode116. 填充每个节点的下一个右侧节点指针
? 题目：116. 填充每个节点的下一个右侧节点指针 (https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/)
? 难度：中等
📕 描述：给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
💡思路：
这个思路也不难，我们增加一个变量来表示前一个节点，让前一个节点的next指向当前节点。
/**
* 116. 填充每个节点的下一个右侧节点指针
*
* @param root
* @return
*/
public Node connect(Node root) {
if (root == null) {
return root;
}
//队列
Deque<Node> queue = new LinkedList();
//根节点
queue.offer(root);
while (!queue.isEmpty()) {
int queueSize = queue.size();
//前一个节点
Node pre = null;
for (int i = 0; i < queueSize; i++) {
Node node = queue.poll();
//每一层的第一个节点
if (i == 0) {
pre = node;
}
//让前点左边节点的next指向当前节点
if (i > 0) {
pre.next = node;
pre = node;
}
//左孩子
if (node.left != null) {
queue.offer(node.left);
}
//右孩子
if (node.right != null) {
queue.offer(node.right);
}
}
}
return root;
}
LeetCode117. 填充每个节点的下一个右侧节点指针 II
? 题目：117. 填充每个节点的下一个右侧节点指针 II (https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/)
? 难度：中等
📕 描述：给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
💡思路：
和上一道题不是基本一模一样嘛？除了不是完美二叉树，但是不影响，一样的代码。
连续做了十道能用一个套路解决的问题，是不是瞬间有种神清气爽，自信澎湃的感觉，我们继续！
由于老三时间和水平有限，所以接下来的题目以递归法为主。
二叉树属性
LeetCode101. 对称二叉树
? 题目：101. 对称二叉树 (https://leetcode-cn.com/problems/symmetric-tree/)
? 难度：简单
📕 描述：给定一个二叉树，检查它是否是镜像对称的。
💡思路：
这题首先是要弄懂，这个镜像对称是什么镜像？
判断二叉树对称，比较的是两棵树（也就是根节点的左右子树）。
注意看，比较看的是T1左侧的元素和T2的右侧的元素；
以及T2左侧的元素和T1右侧的元素。
好了，我们现在看看递归应该怎么实现。
-
递归方法参数和返回值
- 返回值是是否对称，就是布尔类型
- 要比较两个子树，所以参数是左子树节点和右子树节点
-
终止条件
- 都为空指针则返回
true - 有一个为空则返回
false - 两个节点值不相等则返回
false
- 都为空指针则返回
-
递归逻辑
- 判断 T1 的右子树与 T2 的左子树是否对称
- 判断 T1 的左子树与 T2 的右子树是否对称
最后要短路与，只有二者都返回
true最终才为true
来看代码：
/**
* 101. 对称二叉树
*
* @param root
* @return
*/
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
//调用递归函数，比较左孩子，右孩子
return isSymmetric(root.left, root.right);
}
boolean isSymmetric(TreeNode left, TreeNode right) {
//递归终止条件
//1、左右两个节点都为空
if (left == null && right == null) {
return true;
}
//2、两个节点中有一个为空
if (left == null || right == null) {
return false;
}
//3、两个节点的值不相等
if (left.val != right.val) {
return false;
}
//递归左节点的左孩子和右节点的右孩子
boolean outSide = isSymmetric(left.left, right.right);
//递归左节点的右孩子和右节点的左孩子
boolean inSide = isSymmetric(left.right, right.left);
//两种都对称，树才对称
return outSide && inSide;
}
- 🚗时间复杂度：O(n)
LeetCode104. 二叉树的最大深度
? 题目：104. 二叉树的最大深度 (https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
? 难度：简单
📕 描述：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
💡思路：
这道题其实和后序遍历类似。递归左右子树，求出左右子树的深度，其中的最大值再加根节点的深度。
来看看递归怎么写：
-
入参、返参
- 入参是树的根节点，表示树
- 返参是树的深度
-
终止条件
- 根节点为空，表示树空
-
单层逻辑
- 求左子树根的深度l
- 求右子树的深度r
- 两棵子树深度的最大值再加上根节点深度，max(l,r)+1
来看代码：
/**
* 104. 二叉树的最大深度
*
* @param root
* @return
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
int maxDepth = Math.max(leftDepth, rightDepth) + 1;
return maxDepth;
}
- 🚗时间复杂度：O(n)
LeetCode 559. N 叉树的最大深度
? 题目：559. N 叉树的最大深度 (https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/)
? 难度：简单
📕 描述：
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
💡思路：
和上一道思路一样，代码如下：
/**
* 559. N 叉树的最大深度
*
* @param root
* @return
*/
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
int maxDepth = 0;
for (int i = 0; i < root.children.size(); i++) {
int childrenDepth = maxDepth(root.children.get(i));
if (childrenDepth > maxDepth) {
maxDepth = childrenDepth;
}
}
return maxDepth + 1;
}
- 🚗时间复杂度：每个节点遍历一次，所以时间复杂度是 O(N)，其中 NN 为节点数。
LeetCode111. 二叉树的最小深度
? 题目：111. 二叉树的最小深度 (https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/)
? 难度：简单
📕 描述：
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明：**叶子节点是指没有子节点的节点。
💡思路：
乍一看，暗喜，这不和二叉树最大深度一样吗？
仔细一看，不对劲。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
是到最近的叶子节点。如果子树为空，那就没有叶子节点。
所以在我们的单层逻辑里要考虑这种情况，代码如下：
/**
* 111. 二叉树的最小深度
*
* @param root
* @return
*/
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
//左子树
int leftDepth = minDepth(root.left);
//左子树
int rightDepth = minDepth(root.right);
//左子树为空的情况
if (root.left == null && root.right != null) {
return rightDepth + 1;
}
//右子树为空的情况
if (root.right == null && root.left != null) {
return leftDepth + 1;
}
return Math.min(leftDepth, rightDepth) + 1;
}
- 🚗时间复杂度：O(n)
LeetCode222. 完全二叉树的节点个数
? 题目：222. 完全二叉树的节点个数 (https://leetcode-cn.com/problems/count-complete-tree-nodes/)
? 难度：简单
📕 描述：
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
**进阶：**遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
💡思路：
递归方法：
如果要用递归是不是挺简单。左右子树递归，加上根节点。
/**
* 222. 完全二叉树的节点个数
*
* @param root
* @return
*/
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftCount = countNodes(root.left);
int rightCount = countNodes(root.right);
return leftCount + rightCount + 1;
}
- 🚗时间复杂度：O(n)。
利用完全二叉树特性：
我们先来回忆一下什么是完全二叉树：若一棵二叉树至多只有最下面的两层结点的度数可以小于 2, 并且最下一层上的结点都集中在该层最左边的若干位置上， 则此二叉树称为完全二叉树。
完全二叉树有两种情况：
-
满二叉树
-
最后一层节点没满
第1种情况，节点个数=2^k-1（k为树的深度，根节点的深度为0）。
第2种情况，分别递归左孩?，和右孩?，递归到某?深度?定会有左孩?或者右孩?为满?叉树，节点数就可以用2^k-1。
只要树不是满二叉树，就递归左右孩子，知道遇到满二叉树，用公式计算子树的节点数量。
代码如下：
/**
* 222. 完全二叉树的节点个数-利用完全二叉树特性
*
* @param root
* @return
*/
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
//左孩子
TreeNode left = root.left;
//右孩子
TreeNode right = root.right;
int leftHeight = 0, rightHeight = 0;
// 求左?树深度
while (left != null) {
left = left.left;
leftHeight++;
}
// 求右?树深度
while (right != null) {
right = right.right;
leftHeight++;
}
//满二叉树
if (leftHeight == rightHeight) {
return (2 << leftHeight) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
- 🚗时间复杂度：O(logn * logn)
- 🏠 空间复杂度：O(logn)
LeetCode110. 平衡二叉树
? 题目：110. 平衡二叉树 (https://leetcode-cn.com/problems/balanced-binary-tree/)
? 难度：简单
📕 描述：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
💡思路：
在前面，我们做了一道题：104.二叉树的最大深度 。
平衡二叉树的定义是一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
那么我们思路就有了，用前序遍历的方式去判断一个节点以及节点的左右子树是否平衡。
代码如下：
/**
* 110. 平衡二叉树
*
* @param root
* @return
*/
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
//左子树高度
int leftDepth = depth(root.left);
//右子树高度
int rightDepth = depth(root.right);
//当前节点
boolean isRootBalanced = Math.abs(leftDepth - rightDepth) <= 1;
//递归左子树
boolean isLeftBalanced = isBalanced(root.left);
//递归右子树
boolean isRightBalaced = isBalanced(root.right);
//平衡
return isRootBalanced && isLeftBalanced && isRightBalaced;
}
/**
* 获取子树高度
*
* @param root
* @return
*/
public int depth(TreeNode root) {
if (root == null) {
return 0;
}
//左子树高度
int leftDepth = depth(root.left);
//右子树高度
int rightDepth = depth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
- 🚗 时间复杂度：获取子树高度时间复杂度O(n)，判断平衡又要不断递归左右子树，所以时间复杂度为O(n2)。
这种是一种时间复杂度略高的方式，是一种从上往下的判断方式。
还有一种方式，从下往上，类似于二叉树的后序遍历。
/**
* 110. 平衡二叉树-从下往上
*
* @param root
* @return
*/
public boolean isBalanced(TreeNode root) {
return helper(root) != -1;
}
public int helper(TreeNode root) {
if (root == null) {
return 0;
}
//不平衡直接返回-1
//左子树
int left = helper(root.left);
//左子树不平衡
if (left == -1) {
return -1;
}
//右子树
int right = helper(root.right);
//右子树不平衡
if (right == -1) {
return -1;
}
//如果左右子树都是平衡二叉树
//判断左右子树高度差是否小于1
if (Math.abs(left - right) > 1) {
return -1;
}
//返回二叉树中节点的最大高度
return Math.max(left, right) + 1;
}
- 🚗时间复杂度：因为从下往上，每个节点只会遍历到一次，所以时间复杂度为O(n)。
LeetCode404. 左叶子之和
? 题目：404. 左叶子之和(https://leetcode-cn.com/problems/sum-of-left-leaves/)
? 难度：简单
📕 描述：
计算给定二叉树的所有左叶子之和。
💡思路：
这道题题号很危险，但其实不难，重点在于搞清楚什么是左叶子节点？
-
首先，这个节点得是父节点的左孩子，
-
其次，这个节点得是叶子节点。
把这点搞清楚以后，就是一个前序遍历，代码如下：
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
int sum = 0;
//判断根节点的左孩子是否为左叶子
if (root.left != null && root.left.left == null && root.left.right == null) {
sum = root.left.val;
}
//递归左右子树
return sum + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
- 🚗 时间复杂度：O(n)。
LeetCode513. 找树左下角的值
? 题目：513. 找树左下角的值 (https://leetcode-cn.com/problems/find-bottom-left-tree-value/)
? 难度：简单
📕 描述：
给定一个二叉树，在树的最后一行找到最左边的值。
💡思路：
这道题用广度优先遍历比较简单，前面我们已经做过十道广度优先遍历的题目，这里就不再赘言，上代码：
public int findBottomLeftValue(TreeNode root) {
if (root == null) {
return 0;
}
int bottomLeftValue = 0;
//保存节点的队列
Queue<TreeNode> queue = new LinkedList<>();
//加入根节点
queue.offer(root);
while (!queue.isEmpty()) {
int currentSize = queue.size();
//取出队列中的节点
for (int i = 0; i < currentSize; i++) {
//取出队中节点
TreeNode node = queue.poll();
//每层最左边节点
if (i == 0) {
//赋值
bottomLeftValue = node.val;
}
//当前节点左孩子入队
if (node.left != null) {
queue.offer(node.left);
}
//当前节点右孩子入队
if (node.right != null) {
queue.offer(node.right);
}
}
}
return bottomLeftValue;
}
- 🚗时间复杂度：O(n)。
二叉树路径问题
LeetCode257. 二叉树的所有路径
? 题目：257. 二叉树的所有路径 (https://leetcode-cn.com/problems/binary-tree-paths/)
? 难度：简单
📕 描述：
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
💡思路：
可以使用深度优先遍历的方式处理这道题——前序遍历，递归，我们都写熟了的。
但是，这道题不仅仅是递归，还隐藏了回溯。
类比一下我们平时走路，假如说从一个路口，我们想走完所有路口，那么我们该怎么走呢？
那就是我们先沿着一个路口走到头，再回到上一个路口，走另外一个方向。
对于这道题目，回溯的示意图如下：
看一下代码：
/**
* @return java.util.List<java.lang.String>
* @Description: 二叉树的所有路径-回溯初版
* @author 三分恶
* @date 2021/7/14 8:28
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>(32);
if (root == null) {
return result;
}
LinkedList path = new LinkedList();
traversal(root, path, result);
return result;
}
/**
* @return void
* @Description: 遍历
* @author 三分恶
* @date 2021/7/14 8:29
*/
void traversal(TreeNode current, LinkedList path, List<String> result) {
path.add(current.val);
//叶子节点
if (current.left == null && current.right == null) {
StringBuilder sPath = new StringBuilder();
for (int i = 0; i < path.size() - 1; i++) {
sPath.append(path.get(i));
//这个箭头不能忘
sPath.append("->");
}
sPath.append(path.get(path.size() - 1));
result.add(sPath.toString());
return;
}
//递归左子树
if (current.left != null) {
traversal(current.left, path, result);
//回溯
path.removeLast();
}
//递归右子树
if (current.right != null) {
traversal(current.right, path, result);
//回溯
path.removeLast();
}
}
精简一下也是可以的，不过回溯就隐藏了：
/**
* @return java.util.List<java.lang.String>
* @Description: 257. 二叉树的所有路径
* https://leetcode-cn.com/problems/binary-tree-paths/
* @author 三分恶
* @date 2021/7/11 10:11
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>(32);
if (root == null) {
return result;
}
traversal(root, "", result);
return result;
}
/**
* @return void
* @Description: 遍历
* @author 三分恶
* @date 2021/7/11 10:10
*/
void traversal(TreeNode current, String path, List<String> result) {
path += current.val;
//叶子节点
if (current.left == null && current.right == null) {
//将路径加入到结果中
result.add(path);
return;
}
//递归左子树
if (current.left != null) {
traversal(current.left, path + "->", result);
}
//递归右子树
if (current.right != null) {
traversal(current.right, path + "->", result);
}
}
- 🚗 时间复杂度：O(n2)，其中n表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(n)，所以时间复杂度为O(n^2)。
LeetCode112. 路径总和
? 题目：112. 路径总和 (https://leetcode-cn.com/problems/path-sum/)
? 难度：简单
📕 描述：
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
💡思路：
既然路径问题已经开始，我们就连做几道来巩固一下。
一样的思路：递归遍历+回溯
代码如下：
/**
* @return boolean
* @Description:
* @author 三分恶
* @date 2021/7/13 8:34
*/
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return traversal(root, targetSum - root.val);
}
/**
* @return boolean
* @Description: 遍历
* @author 三分恶
* @date 2021/7/14 21:22
*/
boolean traversal(TreeNode current, int count) {
//终止条件
if (current.left == null && current.right == null && count == 0) {
//叶子节点，且计数为0
return true;
}
if (current.left == null && current.right == null) {
//叶子节点
return false;
}
//左子树
if (current.left != null) {
count -= current.left.val;
if (traversal(current.left, count)) {
return true;
}
//回溯，撤销处理结果
count += current.left.val;
}
//右子树
if (current.right != null) {
count -= current.right.val;
if (traversal(current.right, count)) {
return true;
}
count += current.right.val;
}
return false;
}
简化一波，如下：
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return traversal(root, targetSum);
}
private boolean traversal(TreeNode root, int count) {
if (root == null) {
return false;
}
//找到满足条件路径
if (root.left == null && root.right == null && count == root.val) {
return true;
}
return traversal(root.left, count - root.val) || traversal(root.right, count - root.val);
}
- 🚗 时间复杂度：和上一道题一样，O(n2)。
LeetCode113. 路径总和 II
? 题目：113. 路径总和 II (https://leetcode-cn.com/problems/path-sum-ii/)
? 难度：中等
📕 描述：
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
💡思路：
好家伙，这道题不是结合了257和112嘛！
直接先上递归+回溯。
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
//结果
List<List<Integer>> result = new ArrayList<>(32);
if (root == null) {
return result;
}
//路径
LinkedList<Integer> path = new LinkedList();
traversal(root, path, result, targetSum - root.val);
return result;
}
private void traversal(TreeNode root, LinkedList<Integer> path, List<List<Integer>> result, int count) {
//根节点放入路径
path.add(root.val);
//叶子节点,且满足节点总和要求
if (root.left == null && root.right == null && count == 0) {
//注意，这里需要新定义一个path集合,否则result里存储的是path的引用
List<Integer> newPath = new LinkedList<>(path);
//添加路径
result.add(newPath);
return;
}
//如果是叶子节点，直接返回
if (root.left == null && root.right == null) {
return;
}
//递归左子树
if (root.left != null) {
count -= root.left.val;
traversal(root.left, path, result, count);
//回溯
path.removeLast();
count += root.left.val;
}
//递归右子树
if (root.right != null) {
count -= root.right.val;
traversal(root.right, path, result, count);
//回溯
path.removeLast();
count += root.right.val;
}
}
接下来简化一下：
//结果
List<List<Integer>> result = new ArrayList<>(16);
//路径
LinkedList<Integer> path = new LinkedList<>();
/**
* @return java.util.List<java.util.List < java.lang.Integer>>
* @Description: 113. 路径总和 II
* @author 三分恶
* @date 2021/7/12 21:25
*/
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) {
return result;
}
traversal(root, targetSum);
return result;
}
/**
* @return void
* @Description: 深度优先遍历
* @author 三分恶
* @date 2021/7/12 22:03
*/
void traversal(TreeNode root, int sum) {
if (root == null) {
return;
}
//路径和
sum -= root.val;
//添加节点
path.offerLast(root.val);
//到达叶子节点,且路径和满足要求
if (root.left == null && root.right == null && sum == 0) {
result.add(new LinkedList<>(path));
}
//递归左子树
traversal(root.left, sum);
//递归右子树
traversal(root.right, sum);
//回溯
path.pollLast();
}
- 🚗时间复杂度：一样，O(n^2)。
LeetCode437. 路径总和 III
? 题目：437. 路径总和 III (https://leetcode-cn.com/problems/path-sum-iii/)
? 难度：中等
📕 描述：
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
💡思路：
这道题不需要从根节点开始，也不需要在叶子节点结束，所以呢，
- 我们要遍历每一个节点，要额外递归一次
- 获取到符合条件的path，也不要return
下面上代码，直接上精简版的，看了前面一道题，相信原始版递归+回溯 也是小case。
//结果
int result = 0;
public int pathSum(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
//根节点
traversal(root, targetSum);
//左子树递归
pathSum(root.left, targetSum);
//右子树递归
pathSum(root.right, targetSum);
return result;
}
/**
* @return void
* @Description: 深度优先遍历
* @author 三分恶
* @date 2021/7/12 22:03
*/
void traversal(TreeNode root, int sum) {
if (root == null) {
return;
}
//路径和
sum -= root.val;
//不需要到达叶子节点,路径和满足要求即可
if (sum == 0) {
//结果添加
result++;
}
//递归左子树
traversal(root.left, sum);
//递归右子树
traversal(root.right, sum);
}
- 🚗时间复杂度：pathSum会遍历每一个节点，时间复杂度为O(n)，traversal 时间复杂度为O(n)，所以时间复杂度为O(n2)。
有一道题 ——面试题 04.12. 求和路径 (https://leetcode-cn.com/problems/paths-with-sum-lcci/) 和这道题基本一模一样。
?叉树的修改与构造
LeetCode 106. 从中序与后序遍历序列构造二叉树
? 题目：106. 从中序与后序遍历序列构造二叉树 (https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)
? 难度：中等
📕 描述：
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
💡思路：
我们首先来看一棵树，中序遍历和后序遍历是什么样
我们根据中序遍历和后序遍历的特性，可以得出：
- 在后序遍历序列中，最后一个元素是树的根节点
- 在中序遍历序列中，根节点的左边是左子树，根节点的右边是右子树
那么我们怎么还原二叉树呢？
可以拿后序序列的最后一个节点去切分中序序列，然后根据中序序列，再反过来切分后序序列，这样一层一层地切下去，每次后序序列的最后一个元素就是节点的元素。
我们看一下这个过程：
那具体的步骤是什么样呢？
- 如果数组长度为0，说明是空节点。
- 如果不为空，那么取后序数组最后一个元素作为节点元素
- 找到后序数组最后一个元素在中序数组的位置，作为切割点
- 切割中序数组，切成中序左数组（左子树）和中序右数组（右子树）
- 切割后序数组，切成后序左数组和后序右数组
- 递归左、右区间
这里又存在一个问题，我们需要确定，下一轮的起点和终点。
我们拿[inStart，inEnd] 标记中序数组起始和终止位置，拿[postStart，postEnd]标记后序数组起止位置，rootIndex标记根节点位置。
- 左子树-中序数组
inStart = inStart,inEnd = rootIndex - 1 - 左子树-后序数组
postSrart = postStart,postEnd = postStart + ri - is - 1(pe计算过程解释，后续数组的起始位置加上左子树长度-1 就是后后序数组结束位置了，左子树的长度 = 根节点索引-左子树) - 右子树-中序数组
inStart = roootIndex + 1, inEnd = inEnd - 右子树-后序数组
postStart = postStart + rootIndex - inStart, postEnd - 1
![树的计算过程-来源参考[7]](https://img-blog.csdnimg.cn/img_convert/40bf9f8b8d0a9043aec696209adfda4b.png)
代码如下：
/**
* 106. 从中序与后序遍历序列构造二叉树
* https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
* @param inorder
* @param postorder
* @return
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length == 0 || postorder.length == 0) return null;
return buildTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
/**
* @param inorder 中序数组
* @param inStart 中序数组起点
* @param inEnd 中序数组终点
* @param postorder 后序数组
* @param postStart 后序数组起点
* @param postEnd 后序数组终点
* @return
*/
public TreeNode buildTree(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
//没有元素
if (inEnd - inStart < 1) {
return null;
}
//只有一个元素
if (inEnd - inStart == 1) {
return new TreeNode(inorder[inStart]);
}
//后序数组最后一个元素就是根节点
int rootVal = postorder[postEnd - 1];
TreeNode root = new TreeNode(rootVal);
int rootIndex = 0;
//根据根节点，找到该值在中序数组inorder里的位置
for (int i = inStart; i < inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
}
}
//根据rootIndex切割左右子树
root.left = buildTree(inorder, inStart, rootIndex,
postorder, postStart, postStart + (rootIndex - inStart));
root.right = buildTree(inorder, rootIndex + 1, inEnd,
postorder, postStart + (rootIndex - inStart), postEnd - 1);
return root;
}
- 🚗 时间复杂度O(n)。
LeetCode105. 从前序与中序遍历序列构造二叉树
? 题目：105. 从前序与中序遍历序列构造二叉树 (https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
? 难度：中等
📕 描述：
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
💡思路：
和上一道题目类似，先序遍历第一个节点是根节点，拿先序遍历数组第一个元素去切割中序数组，再拿中序数组切割先序数组。
代码如下：
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, 0, preorder.length-1,
inorder, 0, inorder.length-1);
}
public TreeNode buildTree(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
//递归终止条件
if (inStart > inEnd || preStart > preEnd) return null;
//根节点值
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
//根节点下标
int rootIndex = inStart;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
//递归，寻找左右子树
root.left=buildTree(preorder, preStart + 1, preStart + (rootIndex - inStart),
inorder, inStart, rootIndex - 1);
root.right=buildTree(preorder, preStart + (rootIndex - inStart) + 1, preEnd,
inorder, rootIndex + 1, inEnd);
return root;
}
🚗 时间复杂度：O(n)
LeetCode654. 最大二叉树
? 题目：654. 最大二叉树 (https://leetcode-cn.com/problems/maximum-binary-tree/)
? 难度：中等
📕 描述：
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
- 二叉树的根是数组 nums 中的最大元素。
- 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
- 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。
示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
示例 2：
输入：nums = [3,2,1]
输出：[3,null,2,null,1]
💡 思路：
这个就好说了，题目里面都给出了解法，nums最大元素是根节点，然后再递归最大元素左右部分。
代码如下：
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructMaximumBinaryTree(nums, 0, nums.length);
}
public TreeNode constructMaximumBinaryTree(int[] nums, int start, int end) {
//没有元素
if (end - start < 1) {
return null;
}
//只剩一个元素
if (end - start == 1) {
return new TreeNode(nums[start]);
}
//最大值位置
int maxIndex = start;
//最大值
int maxVal = nums[start];
for (int i = start + 1; i < end; i++) {
if (nums[i] > maxVal) {
maxVal = nums[i];
maxIndex = i;
}
}
//根节点
TreeNode root = new TreeNode(maxVal);
//递归左半部分
root.left = constructMaximumBinaryTree(nums, start, maxIndex);
//递归右半部分
root.right = constructMaximumBinaryTree(nums, maxIndex + 1, end);
return root;
}
- 🚗 时间复杂度 ：找到数组最大值时间复杂度O(n)，递归时间复杂度O(n)，所以总的时间复杂度O(n2)。
LeetCode617. 合并二叉树
? 题目：617. 合并二叉树 (https://leetcode-cn.com/problems/merge-two-binary-trees/)
? 难度：简单
📕 描述：
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
💡思路：
做个简单题找下信心。
这道题啥情况呢？
这不就前序遍历根、左、右嘛。
虽然题目里没要求不能改变原来的树结构，但是，我们还是用一棵新树来合并两棵树。
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
//递归结束条件，有一个节点为空
if (root1 == null || root2 == null) {
return root1 == null ? root2 : root1;
}
//新树
TreeNode root = new TreeNode(0);
//合并
root.val = root1.val + root2.val;
//左子树
root.left = mergeTrees(root1.left, root2.left);
//右子树
root.right = mergeTrees(root1.right, root2.right);
return root;
}
- 🚗 时间复杂度：O(n)。
求?叉搜索树的属性
二叉搜索树我们前面也了解了，左小右大，接下来我们开始看看二叉搜索树相关题目。
LeetCode700. 二叉搜索树中的搜索
? 题目：700. 二叉搜索树中的搜索 (https://leetcode-cn.com/problems/search-in-a-binary-search-tree/)
? 难度：简单
📕 描述：
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如，
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和值: 2
你应该返回如下子树:
2
/ \
1 3
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
💡 思路：
这也没啥好说的吧，前序遍历就行了。
只不过递归左右子树的时候，我们可以利用左小右大的特性。
📜代码如下：
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
//递归左子树
if (val < root.val) {
return searchBST(root.left, val);
}
//递归右子树
if (val > root.val) {
return searchBST(root.right, val);
}
return null;
}
- 🚗 时间复杂度：O(logn)。
LeetCode98. 验证二叉搜索树
? 题目：98. 验证二叉搜索树(https://leetcode-cn.com/problems/validate-binary-search-tree/)
? 难度：简单
📕 描述：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
💡 思路：
我们知道，中序遍历二叉搜索树，输出的是有序序列，所以上中序遍历。
在root比较的时候呢，我们可以把root和上一个root比较。
📜代码如下：
class Solution {
private TreeNode pre;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
//左子树
boolean isValidLeft = isValidBST(root.left);
if (!isValidLeft){
return false;
}
//根
if (pre!=null&&pre.val>=root.val){
return false;
}
pre=root;
//右子树
boolean isValidRight = isValidBST(root.right);
return isValidRight;
}
}
- 🚗 时间复杂度O(n)
LeetCode530. 二叉搜索树的最小绝对差
? 题目：98. 验证二叉搜索树(https://leetcode-cn.com/problems/validate-binary-search-tree/)
? 难度：简单
📕 描述：
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
输入：
1
\
3
/
2
输出：
1
解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
💡 思路：
二叉搜索树的中序遍历是有序的。
那和上一道题一样，中序遍历。我们同样记录上一个遍历的节点，然后取和当前节点差值的最大值。
📜代码如下：
class Solution {
TreeNode pre;
Integer res = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
dfs(root);
return res;
}
public void dfs(TreeNode root) {
if (root == null) {
return;
}
//左
getMinimumDifference(root.left);
//中
if (pre != null) {
res = Math.min(res, root.val-pre.val);
}
pre=root;
//右
getMinimumDifference(root.right);
}
}
- 🚗 时间复杂度O(n)
LeetCode501. 二叉搜索树中的众数
? 题目：501. 二叉搜索树中的众数 (https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/)
? 难度：简单
📕 描述：
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],
1
\
2
/
2
返回[2].
提示：如果众数超过1个，不需考虑输出顺序
**进阶：**你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内
💡 思路：
如果是二叉树求众数，我们能想到的办法就是引入map来统计高频元素集合。
但是二叉搜索树，我们接着用它的中序遍历有序这个特性。
用prev表示前一个节点，用count表示当前值的数量，用maxCount表示重复数字的最大数量，使用列表存储结果。
-
如果节点值等于prev，count就加1，
-
如果节点不等于prev，说明遇到了下一个新的值，更新prev为新的值，然后让count=1；
- 如果count==maxCount，就把当前节点的值加入到集合list中。
- 如果count>maxCount，先把list集合清空，然后再把当前节点的值加入到集合list中，最后在更新maxCount的值。
📜代码如下：
class Solution {
//记录当前个数
int count = 0;
//最大个数
int maxCount = 1;
//前驱
TreeNode pre=new TreeNode(0);
//存储众数列表
List<Integer> res = new ArrayList<>();
public int[] findMode(TreeNode root) {
dfs(root);
int[] ans = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
ans[i] = res.get(i);
}
return ans;
}
public void dfs(TreeNode root) {
if (root == null) return;
//左
dfs(root.left);
//中
if (root.val == pre.val) {
//如果和前一个相同，count++
count++;
} else {
//否则
//pre往后
pre = root;
//count刷新为1
count = 1;
}
//如果是出现次数最多的值
if (count == maxCount) {
res.add(root.val);
} else if (count > maxCount) {
//如果超过最多出现次数
//清空结果结合
res.clear();
//加入新的max元素
res.add(root.val);
//刷新max计数
maxCount = count;
}
//右
dfs(root.right);
}
}
- 🚗 时间复杂度：O(n)
- 🏠 空间复杂度：O(n)
?叉树公共祖先问题
LeetCode236. 二叉树的最近公共祖先
? 题目：501. 二叉搜索树中的众数 (https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/)
? 难度：简单
📕 描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
💡 思路：
我们想啊，查找公共祖先，要是我们能从两个节点往回走就好了。
那有什么办法呢？
还记得我们前面做路径问题的时候吗？我们用到了一个方法——回溯。
大家看一下这个顺序是什么？左、右、根,这不是后序遍历嘛！
那怎么判断一个节点是节点q和节点p的公共祖先呢？有哪几种情况呢？
- q和q都是该节点的子树，而且异侧（p左q右或者p右q左）
- q在p的子树中
- q在p的子树中
那这个后序的递归，又该怎么写呢？
我们看看递归三要素[8]：
- 入参和返回值
需要递归函数返回节点值，来告诉我们是否找到节点q或者p。
- 终止条件
如果找到了 节点p或者q，或者遇到空节点，就返回。
- 单层递归逻辑
我们需要判断是否找到了p和q.
-
当 leftleftleft 和 rightrightright 同时为空 ：说明 root的左 / 右子树中都不包含 p,q，返回 null；
-
当 left 和 right 同时不为空 ：说明 p,q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root为最近公共祖先，返回 root
-
当 leftleftleft 为空 ，right不为空 ：p,q 都不在 root的左子树中，直接返回 right。具体可分为两种情况：
- p,q 其中一个在 root 的 右子树 中，此时 right指向 p（假设为 p ）
- p,q 两节点都在 root的 右子树 中，此时的 right 指向 最近公共祖先节点
-
当 left不为空 ， right为空 ：与情况
3.同理；
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//递归结束条件
if (root == null || root == p || root == q) return root;
//左
TreeNode left = lowestCommonAncestor(root.left, p, q);
//右
TreeNode right = lowestCommonAncestor(root.right, p, q);
//四种情况判断
//left和right同时为空
if (left == null && right == null) {
return null;
}
//left和right同时不为空
if (left != null && right != null) {
return root;
}
//left为空，right不为空
if (left == null && right != null) {
return right;
}
//left不为空，right为空
if (left != null && right == null) {
return left;
}
return null;
}
精简一下代码：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//递归结束条件
if (root == null || root == p || root == q) return root;
//左
TreeNode left = lowestCommonAncestor(root.left, p, q);
//右
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
if (left == null) return right;
return left;
}
- 🚗 时间复杂度：O(n)。
LeetCode235. 二叉搜索树的最近公共祖先
? 题目：501. 二叉搜索树中的众数 (https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/)
? 难度：简单
📕 描述：
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
💡 思路：
接着我们来看二叉搜索树的最近公共祖先，我们可以直接用二叉树的最近公共祖先的方法给它来一遍。
但是有没有可能能利用到我们二叉搜索树的特性呢？
当然可以。
我们的二叉树的节点是左小右大的特性，只要当前节点在[p,q]之间，就可以确定当前节点是最近公共祖先。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
//左
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}
//右
if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
- 🚗 时间复杂度：O(n)
?叉搜索树的修改与构造
LeetCode701. 二叉搜索树中的插入操作
? 题目：701. 二叉搜索树中的插入操作 (https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
? 难度：中等
📕 描述：
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1：
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：
💡 思路：
注意：这道题是没有限制插入的方式的。
像题目示例中，给出了两种情况：
- 第一种：占别人的位置，可以看到5和4的位置做了调整，让树满足平衡二叉树的要求，但是这种实现起来肯定麻烦
- 第二种：我们其实可以偷个懒，找个空位呗，我们通过搜索，找到一个符合大小关系的叶子节点，把它插入到叶子节点的子树。
代码如下：
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
//左
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
}
//右
if (val > root.val) {
root.right = insertIntoBST(root.right, val);
}
return root;
}
- 🚗 时间复杂度：O(n)。
LeetCode450. 删除二叉搜索树中的节点
? 题目：701. 二叉搜索树中的插入操作 (https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
? 难度：中等
📕 描述：
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
示例:
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
5
/ \
4 6
/ \
2 7
另一个正确答案是 [5,2,6,null,4,null,7]。
5
/ \
2 6
\ \
4 7
💡 思路：
哦吼，上道题我们偷了懒，但是这道题没法偷懒了。
删除一个节点，就相当于挖了个坑，我们就得想办法把它填上，而且还得让二叉树符合平衡二叉树的定义。
找到删除节点，我们把所有的情况列出来：
- 左右孩子都为空（叶子节点），直接删除节点
- 删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位
- 删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位
被删除节点左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子），放到删除节点的右子树的最左节点的左孩子上。这句话很绕对不对，我们拿图说话。
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
//找到被删除节点
if (root.val == key) {
//1. 左右孩子都为空（叶子节点）
if (root.left == null && root.right == null) return null;
//2. 左孩子为空，右孩子不为空
if (root.left == null) return root.right;
//3. 右孩子为空，左孩子不空
if (root.right == null) return root.left;
//4.左右孩子都不为空
if (root.left != null && root.right != null) {
//寻找右子树最左节点
TreeNode node = root.right;
while (node.left != null) {
node = node.left;
}
//把要删除节点的左子树放在node左子树位置
node.left = root.left;
//把root节点保存一下，准备删除
TreeNode temp = root;
//root右孩子作为新的根节点
root = root.right;
return root;
}
}
//左孩子
if (key < root.val) root.left = deleteNode(root.left, key);
//右孩子
if (key > root.val) root.right = deleteNode(root.right, key);
return root;
}
代码点臃肿，但是每种情况都很清晰，懒得再精简了。
- 🚗 时间复杂度：O(n)。
LeetCode669. 修剪二叉搜索树
? 题目：701. 二叉搜索树中的插入操作 (https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
? 难度：中等
📕 描述：
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
示例 1：
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
💡 思路：
修剪的示意图：
大概的过程是什么样呢？
遍历二叉树：
- 当前节点如果是在[low，high]内，继续向下遍历
- 当前节点小于low时候，是需要剪枝的节点，查找它的右子树，找到在[low，high]区间的节点
- 如果当前节点大于high的时候，是需要剪枝的节点，查找它的左子树，找到在[low，high]区间的节点
代码如下：
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return null;
if (root.val < low) {
return trimBST(root.right, low, high);
}
if (root.val > high) {
return trimBST(root.left, low, high);
}
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
- 🚗 时间复杂度：O(n)。
LeetCode538. 把二叉搜索树转换为累加树
? 题目：701. 二叉搜索树中的插入操作 (https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
? 难度：中等
📕 描述：
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
💡思路：
这个题怎么办呢？
如果是数组[3,5,6] 我们马上就能想到，从后往前累加呗。
但是这是个二叉搜索树，我们知道二叉搜索树的中序序列是一个有序序列，那我们把中序倒过来不就行了。
中序是左、右、中,我们改成右、中、左。
class Solution {
int preVal = 0;
public TreeNode convertBST(TreeNode root) {
dfs(root);
return root;
}
public void dfs(TreeNode root) {
if (root == null) return;
//倒中序，右左中
dfs(root.right);
root.val += preVal;
preVal = root.val;
dfs(root.left);
}
}
- 🚗 时间复杂度：O(n)。
总结
顺口溜总结来了：
简单的事情重复做，重复的事情认真做，认真的事情有创造性地做！
我是
三分恶，一个能文能武的全栈开发。
点赞、关注不迷路，大家下期见！
博主是个算法萌新，刷题思路和路线主要参考了以下大佬！建议关注！
参考：
[1]. https://github.com/youngyangyang04/leetcode-master
[2]. https://labuladong.gitbook.io/algo/
[3]. https://leetcode-cn.com/u/sdwwld/
[4]. https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/qing-song-ji-yi-er-cha-shu-de-qian-zhong-6vu5/
[5]. https://leetcode-cn.com/problems/binary-tree-paths/solution/yi-pian-wen-zhang-jie-jue-suo-you-er-cha-5f58/
[6]. https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/
[7].https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/tu-jie-gou-zao-er-cha-shu-wei-wan-dai-xu-by-user72/
[8].https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/
[9]. https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/javachao-jian-dan-de-er-fen-sou-suo-di-g-z83v/