LeetCode通关：连刷三十九道二叉树，刷疯了！⭐四万字长文搞定二叉树，建议收藏！⭐

那么先从二叉树的前序遍历开始吧。

☕ 题目：LeetCode144. 二叉树的前序遍历 (https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)

❓ 难度：简单

📕 描述：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

💡 思路：

☕ 题目：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;}

• 🚗时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。

好了，二叉树的深度优先遍历和广度优先遍历的基础已经完成了，接下来，我们看一看，在这两种遍历的基础上衍生出的各种变化吧！

☕ 题目：剑指 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()) {//当前队列sizeint 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()) {//维护队列当前sizeint 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

• 递归逻辑

  • 判断 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)

☕ 题目：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)

☕ 题目：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 为节点数。

☕ 题目：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)

☕ 题目：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. 最后一层节点没满

第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)

☕ 题目：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(n²)。

这种是一种时间复杂度略高的方式，是一种从上往下的判断方式。

还有一种方式，从下往上，类似于二叉树的后序遍历。

   /*** 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;}//如果左右子树都是平衡二叉树//判断左右子树高度差是否小于1if (Math.abs(left - right) > 1) {return -1;}//返回二叉树中节点的最大高度return Math.max(left, right) + 1;}

• 🚗时间复杂度：因为从下往上，每个节点只会遍历到一次，所以时间复杂度为O(n)。

☕ 题目：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)。

☕ 题目：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)。

☕ 题目：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(n²)，其中n表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(n)，所以时间复杂度为O(n^2)。

☕ 题目：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) {//叶子节点，且计数为0return 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(n²)。

☕ 题目：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)。

☕ 题目：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(n²)。

有一道题 ——面试题 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/)

❓ 难度：中等

📕 描述：

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

💡思路：

我们首先来看一棵树，中序遍历和后序遍历是什么样

我们根据中序遍历和后序遍历的特性，可以得出：

• 在后序遍历序列中，最后一个元素是树的根节点
• 在中序遍历序列中，根节点的左边是左子树，根节点的右边是右子树

那么我们怎么还原二叉树呢？

可以拿后序序列的最后一个节点去切分中序序列，然后根据中序序列，再反过来切分后序序列，这样一层一层地切下去，每次后序序列的最后一个元素就是节点的元素。

我们看一下这个过程：

那具体的步骤是什么样呢？

• 如果数组长度为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

代码如下：

    /*** 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)。

☕ 题目：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 中的最大元素。
• 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
• 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。

返回有给定数组 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(n²)。

☕ 题目：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)。

☕ 题目：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)。

☕ 题目：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)

☕ 题目：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)

☕ 题目：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表示重复数字的最大数量，使用列表存储结果。

1. 如果节点值等于prev，count就加1，

2. 如果节点不等于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刷新为1count = 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)

☕ 题目：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的公共祖先呢？有哪几种情况呢？

1. q和q都是该节点的子树，而且异侧（p左q右或者p右q左）
2. q在p的子树中
3. q在p的子树中

那这个后序的递归，又该怎么写呢？

我们看看递归三要素[8]：

• 入参和返回值

需要递归函数返回节点值，来告诉我们是否找到节点q或者p。

• 终止条件

如果找到了 节点p或者q，或者遇到空节点，就返回。

• 单层递归逻辑

我们需要判断是否找到了p和q.

1. 当 leftleftleft 和 rightrightright 同时为空 ：说明 root的左 / 右子树中都不包含 p,q，返回 null；

2. 当 left 和 right 同时不为空 ：说明 p,q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root为最近公共祖先，返回 root

3. 当 leftleftleft 为空 ，right不为空 ：p,q 都不在 root的左子树中，直接返回 right。具体可分为两种情况：

   1. p,q 其中一个在 root 的 右子树 中，此时 right指向 p（假设为 p ）
   2. p,q 两节点都在 root的 右子树 中，此时的 right 指向 最近公共祖先节点

4. 当 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)。

☕ 题目：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)

☕ 题目：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)。

☕ 题目：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 = 35/ \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

💡 思路：

哦吼，上道题我们偷了懒，但是这道题没法偷懒了。

删除一个节点，就相当于挖了个坑，我们就得想办法把它填上，而且还得让二叉树符合平衡二叉树的定义。

找到删除节点，我们把所有的情况列出来：

1. 左右孩子都为空（叶子节点），直接删除节点

2. 删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位

3. 删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位

4. 被删除节点左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子），放到删除节点的右子树的最左节点的左孩子上。这句话很绕对不对，我们拿图说话。

    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)。

☕ 题目：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)。

☕ 题目：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)。