分门别类刷算法，坚持，进步！
!! 刷题路线参考：https://github.com/youngyangyang04/leetcode-master
大家好， 这一节我们来刷二叉树，二叉树相关题目在面试里非常高频，而且在力扣里数量很多，足足有几百道，不要慌，我们一步步来。我的文章很长，你们 收藏一下。
二叉树是一种比较常见的数据结构，在开始刷二叉树之前，先简单了解一下一些二叉树的基础知识。更详细的数据结构知识建议学习《数据结构与算法》。
二叉树是每个节点至多有两棵子树的树。
二叉树主要的两种形式：满二叉树和完全二叉树。
满⼆叉树：如果⼀棵⼆叉树只有度为0的结点和度为2的结点，并且度为0的结点在同⼀层上，则这棵⼆
叉树为满⼆叉树。一棵深度为k的满二叉树节点个数为2^k^ -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. 二叉树的前序遍历 (https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)
❓ 难度：简单
描述：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
思路：
我们前面看了递归三要素，接下来我们开始用递归法来进行二叉树的前序遍历：
void preOrderRecu(TreeNode root, List<Integer> nodes)
2 . 确定终⽌条件：递归结束也很简单，如果当前遍历的这个节点是空，就直接return，代码如下：
//递归结束条件
if (root == null) {
return;
}3 . 确定单层递归的逻辑：前序遍历是根左右的顺序，所以在单层递归的逻辑里，先取根节点的值，再递归左子树和右子树，代码如下：
//添加根节点
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);
});
}复杂度：
递归法会者不难，难者不会。只要能理解，这个是不是很轻松？
我们接下来，搞一下稍微麻烦一点的迭代法。
迭代法的原理是引入新的数据结构，用来存储遍历的节点。
递归的过程是不断往左边走，当递归终止的时候，就添加节点。现在使用迭代，我们需要自己来用一个数据结构存储节点。
那么用什么数据结构比较合适呢？我们自然而然地想到——栈。
迭代法的核心是：借助栈结构，模拟递归的过程，需要注意何时出栈入栈，何时访问结点。
前序遍历地顺序是根左右，先把根和左子树入栈，再将栈中的元素慢慢出栈，如果右子树不为空，就把右子树入栈。
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;
}☕ 题目：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;
}☕ 题目：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;
}☕ 题目：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;
}好了，二叉树的深度优先遍历和广度优先遍历的基础已经完成了，接下来，我们看一看，在这两种遍历的基础上衍生出的各种变化吧！
我们首先来看一下在层序遍历的基础上，稍微有一些变化的题目。
☕ 题目：剑指 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(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;
}☕ 题目：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;
}☕ 题目：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;
}☕ 题目：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;
}☕ 题目：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;
}☕ 题目：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;
}☕ 题目：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;
}☕ 题目：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。
思路：
和上一道题不是基本一模一样嘛？除了不是完美二叉树，但是不影响，一样的代码。
连续做了十道能用一个套路解决的问题，是不是瞬间有种神清气爽，自信澎湃的感觉，我们继续！
!! 由于老三时间和水平有限，所以接下来的题目以递归法为主。
☕ 题目：101. 对称二叉树 (https://leetcode-cn.com/problems/symmetric-tree/)
❓ 难度：简单
描述：给定一个二叉树，检查它是否是镜像对称的。
思路：
这题首先是要弄懂，这个镜像对称是什么镜像？
判断二叉树对称，比较的是两棵树（也就是根节点的左右子树）。
注意看，比较看的是T1左侧的元素和T2的右侧的元素；
以及T2左侧的元素和T1右侧的元素。
好了，我们现在看看递归应该怎么实现。
递归方法参数和返回值
返回值是是否对称，就是布尔类型
要比较两个子树，所以参数是左子树节点和右子树节点
终止条件
都为空指针则返回 true
有一个为空则返回 false
两个节点值不相等则返回 false
递归逻辑
最后要短路与，只有二者都返回true最终才为true
判断 T1 的右子树与 T2 的左子树是否对称
判断 T1 的左子树与 T2 的右子树是否对称
来看代码：
/**
* 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;
}☕ 题目：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;
}☕ 题目：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;
}☕ 题目：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;
}☕ 题目：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;
}利用完全二叉树特性：
我们先来回忆一下什么是完全二叉树：若一棵二叉树至多只有最下面的两层结点的度数可以小于 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;
}☕ 题目：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;
}这种是一种时间复杂度略高的方式，是一种从上往下的判断方式。
还有一种方式，从下往上，类似于二叉树的后序遍历。
/**
* 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;
}☕ 题目：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);
}☕ 题目：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;
}☕ 题目：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);
}
}☕ 题目：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);
}☕ 题目：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();
}☕ 题目：437. 路径总和 III (https://leetcode-cn.com/problems/path-sum-iii/)
❓ 难度：中等
描述：
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
思路：
这道题不需要从根节点开始，也不需要在叶子节点结束，所以呢，
下面上代码，直接上精简版的，看了前面一道题，相信原始版递归+回溯 也是小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);
}有一道题 ——面试题 04.12. 求和路径 (https://leetcode-cn.com/problems/paths-with-sum-lcci/) 和这道题基本一模一样。
☕ 题目：106. 从中序与后序遍历序列构造二叉树 (https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)
❓ 难度：中等
描述：
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
思路：
我们首先来看一棵树，中序遍历和后序遍历是什么样
我们根据中序遍历和后序遍历的特性，可以得出：
那么我们怎么还原二叉树呢？
可以拿后序序列的最后一个节点去切分中序序列，然后根据中序序列，再反过来切分后序序列，这样一层一层地切下去，每次后序序列的最后一个元素就是节点的元素。
我们看一下这个过程：
那具体的步骤是什么样呢？
这里又存在一个问题，我们需要确定，下一轮的起点和终点。
我们拿[inStart，inEnd] 标记中序数组起始和终止位置，拿[postStart，postEnd]标记后序数组起止位置，rootIndex标记根节点位置。
inStart = inStart, inEnd = rootIndex - 1postSrart = postStart, postEnd = postStart + ri - is - 1 (pe计算过程解释，后续数组的起始位置加上左子树长度-1 就是后后序数组结束位置了，左子树的长度 = 根节点索引-左子树)inStart = roootIndex + 1, inEnd = inEndpostStart = postStart + rootIndex - inStart, postEnd - 1
代码如下：
/**
* 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;
}☕ 题目：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)
☕ 题目：654. 最大二叉树 (https://leetcode-cn.com/problems/maximum-binary-tree/)
❓ 难度：中等
描述：
给定一个不含重复元素的整数数组 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 = constructMaximumBin