- 刷题指南">刷题指南
- 226. 翻转二叉树">226. 翻转二叉树
- 116. 填充每个节点的下一个右侧节点指针">116. 填充每个节点的下一个右侧节点指针
- ">
- 114. 二叉树展开为链表">114. 二叉树展开为链表
- 654. 最大二叉树">654. 最大二叉树
- 106. 从中序与后序遍历序列构造二叉树">106. 从中序与后序遍历序列构造二叉树
- 652. 寻找重复的子树">652. 寻找重复的子树
- 230. 二叉搜索树中第K小的元素">230. 二叉搜索树中第K小的元素
- 538. 把二叉搜索树转换为累加树">538. 把二叉搜索树转换为累加树
- 450. 删除二叉搜索树中的节点">450. 删除二叉搜索树中的节点
- 701. 二叉搜索树中的插入操作">701. 二叉搜索树中的插入操作
- 700. 二叉搜索树中的搜索">700. 二叉搜索树中的搜索
- 98. 验证二叉搜索树">98. 验证二叉搜索树
- 96. 不同的二叉搜索树">96. 不同的二叉搜索树
刷题指南
226. 翻转二叉树
学习链接链接
只要把二叉树上的每一个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树。
/*** Definition for a binary tree node.* 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;* }* }*/class Solution {public TreeNode invertTree(TreeNode root) {// 边界判断if(root==null){return null;}// 左右节点交换TreeNode temp=root.left;root.left=root.right;root.right=temp;// 递归这个过程invertTree(root.left);invertTree(root.right);return root;}}
首先讲这道题目是想告诉你，二叉树题目的一个难点就是，如何把题目的要求细化成每个节点需要做的事情。
值得一提的是，如果把交换左右子节点的代码放在后序遍历的位置也是可以的，但是放在中序遍历的位置是不行的，请你想一想为什么？
116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node left;
Node right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
// 主函数Node connect(Node root) {if (root == null) return null;connectTwoNode(root.left, root.right);return root;}// 辅助函数void connectTwoNode(Node node1, Node node2) {if (node1 == null || node2 == null) {return;}/**** 前序遍历位置 ****/// 将传入的两个节点连接node1.next = node2;// 连接相同父节点的两个子节点connectTwoNode(node1.left, node1.right);connectTwoNode(node2.left, node2.right);// 连接跨越父节点的两个子节点connectTwoNode(node1.right, node2.left);}
114. 二叉树展开为链表
class Solution {public void flatten(TreeNode root) {// 边界判断if(root==null){return ;}flatten(root.left);flatten(root.right);// 递归调用，把左右子树分别拉成一条链TreeNode left= root.left;TreeNode right = root.right;// 把左子树变成右子树root.left=null;root.right=left;// 把右子树接到左子树上TreeNode p=root;while(p.right!=null){p=p.right;}p.right=right;}}
把题目的要求细化，搞清楚根节点应该做什么，然后剩下的事情抛给前/中/后序的遍历框架就行了
654. 最大二叉树
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
- 二叉树的根是数组 nums 中的最大元素。
- 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
- 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。 ```java / 主函数 / TreeNode constructMaximumBinaryTree(int[] nums) { return build(nums, 0, nums.length - 1); }
/ 将 nums[lo..hi] 构造成符合条件的树，返回根节点 / TreeNode build(int[] nums, int lo, int hi) { // base case if (lo > hi) { return null; }
// 找到数组中的最大值和对应的索引int index = -1, maxVal = Integer.MIN_VALUE;for (int i = lo; i <= hi; i++) {if (maxVal < nums[i]) {index = i;maxVal = nums[i];}}TreeNode root = new TreeNode(maxVal);// 递归调用构造左右子树root.left = build(nums, lo, index - 1);root.right = build(nums, index + 1, hi);return root;
}
<a name="SzMvk"></a>
#### [105. 从前序与中序遍历序列构造二叉树](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。<br />核心思想<br /><br />
```java
int leftSize = index - inStart;
root.left = build(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftSize + 1, preEnd,
inorder, index + 1, inEnd);
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
TreeNode build(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd) {
return null;
}
// root 节点对应的值就是前序遍历数组的第一个元素
int rootVal = preorder[preStart];
// rootVal 在中序遍历数组中的索引
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
int leftSize = index - inStart;
// 先构造出当前根节点
TreeNode root = new TreeNode(rootVal);
// 递归构造左右子树
root.left = build(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, index - 1);
root.right = build(preorder, preStart + leftSize + 1, preEnd,
inorder, index + 1, inEnd);
return root;
}
}
我们的主函数只要调用build函数即可，你看着函数这么多参数，解法这么多代码，似乎比我们上面讲的那道题难很多，让人望而生畏，实际上呢，这些参数无非就是控制数组起止位置的，画个图就能解决了。
106. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
核心
int leftSize = index - inStart;
root.left = build(inorder, inStart, index - 1,
postorder, postStart, postStart + leftSize - 1);
root.right = build(inorder, index + 1, inEnd,
postorder, postStart + leftSize, postEnd - 1);
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
TreeNode build(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd) {
return null;
}
// root 节点对应的值就是后序遍历数组的最后一个元素
int rootVal = postorder[postEnd];
// rootVal 在中序遍历数组中的索引
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
// 左子树的节点个数
int leftSize = index - inStart;
TreeNode root = new TreeNode(rootVal);
// 递归构造左右子树
root.left = build(inorder, inStart, index - 1,
postorder, postStart, postStart + leftSize - 1);
root.right = build(inorder, index + 1, inEnd,
postorder, postStart + leftSize, postEnd - 1);
return root;
}
}
有了前一题的铺垫，这道题很快就解决了，无非就是rootVal变成了最后一个元素，再改改递归函数的参数而已，只要明白二叉树的特性，也不难写出来。
最后呼应下前文，做二叉树的问题，关键是把题目的要求细化，搞清楚根节点应该做什么，然后剩下的事情抛给前/中/后序的遍历框架就行了。
652. 寻找重复的子树
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
如果你想知道以自己为根的子树是不是重复的，是否应该被加入结果列表中，你需要知道什么信息？
你需要知道以下两点：
1、以我为根的这棵二叉树（子树）长啥样？
2、以其他节点为根的子树都长啥样？
其实看到这个问题，就可以判断本题要使用「后序遍历」框架来解决：
void traverse(TreeNode root) {
traverse(root.left);
traverse(root.right);
/ 解法代码的位置 /
}
为什么？很简单呀，我要知道以自己为根的子树长啥样，是不是得先知道我的左右子树长啥样，再加上自己，就构成了整棵子树的样子？
我们借助一个外部数据结构，让每个节点把自己子树的序列化结果存进去
class Solution {
// 记录所有子树以及出现的次数
HashMap<String, Integer> memo = new HashMap<>();
// 记录重复的子树根节点
LinkedList<TreeNode> res = new LinkedList<>();
/* 主函数 */
List<TreeNode> findDuplicateSubtrees(TreeNode root) {
traverse(root);
return res;
}
/* 辅助函数 */
String traverse(TreeNode root) {
if (root == null) {
return "#";
}
String left = traverse(root.left);
String right = traverse(root.right);
String subTree = left + "," + right+ "," + root.val;
int freq = memo.getOrDefault(subTree, 0);
// 多次重复也只会被加入结果集一次
if (freq == 1) {
res.add(root);
}
// 给子树对应的出现次数加一
memo.put(subTree, freq + 1);
return subTree;
}
}
getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
getOrDefault() 方法的语法为：
hashmap.get(Object key, V defaultValue)
注：hashmap 是 HashMap 类的一个对象。
230. 二叉搜索树中第K小的元素
难度中等
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
class Solution {
int res;
int index;
public int kthSmallest(TreeNode root, int k) {
build(root,k);
return res;
}
public void build(TreeNode root,int k){
if(root==null){
return;
}
build(root.left,k);
index++;
if(k==index){
res=root.val;
return;
}
build(root.right,k);
}
}
思路就是升序排序，然后找第k个元素呗。BST 的中序遍历其实就是升序排序的结果，找第k个元素肯定不是什么难事。
538. 把二叉搜索树转换为累加树
难度中等
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
题目应该不难理解，比如图中的节点 5，转化成累加树的话，比 5 大的节点有 6，7，8，加上 5 本身，所以累加树上这个节点的值应该是 5+6+7+8=26。
void traverse(TreeNode root) {
if (root == null) return;
// 先递归遍历右子树
traverse(root.right);
// 中序遍历代码位置
print(root.val);
// 后递归遍历左子树
traverse(root.left);
}
这段代码可以从大到小降序打印 BST 节点的值，如果维护一个外部累加变量sum，然后把sum赋值给 BST 中的每一个节点，不就将 BST 转化成累加树了吗？
TreeNode convertBST(TreeNode root) {
traverse(root);
return root;
}
// 记录累加和
int sum = 0;
void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.right);
// 维护累加和
sum += root.val;
// 将 BST 转化成累加树
root.val = sum;
traverse(root.left);
}
450. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
这个问题稍微复杂，跟插入操作类似，先「找」再「改」，先把框架写出来再说：
TreeNode deleteNode(TreeNode root, int key) {
if (root.val == key) {
// 找到啦，进行删除
} else if (root.val > key) {
// 去左子树找
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
// 去右子树找
root.right = deleteNode(root.right, key);
}
return root;
}
找到目标节点了，比方说是节点 A，如何删除这个节点，这是难点。因为删除节点的同时不能破坏 BST 的性质。有三种情况，用图片来说明。
情况 1：A 恰好是末端节点，两个子节点都为空，那么它可以当场去世了。
if (root.left == null && root.right == null)
return null;
情况 2：A 只有一个非空子节点，那么它要让这个孩子接替自己的位置。
// 排除了情况 1 之后
if (root.left == null) return root.right;
if (root.right == null) return root.left;
情况 3：A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我们以第二种方式讲解。
if (root.left != null && root.right != null) {
// 找到右子树的最小节点
TreeNode minNode = getMin(root.right);
// 把 root 改成 minNode
root.val = minNode.val;
// 转而去删除 minNode
root.right = deleteNode(root.right, minNode.val);
}
三种情况分析完毕，填入框架，简化一下代码：
找右子树最小替换待删结点
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null){
return null;
}
if(root.val==key){
if(root.left==null){
return root.right;
}
if(root.right==null){
return root.left;
}
TreeNode minNode=getMin(root.right);
root.val=minNode.val;
root.right=deleteNode(root.right,minNode.val);
}else if(root.val>key){
root.left=deleteNode(root.left,key);
}else if(root.val<key){
root.right=deleteNode(root.right,key);
}
return root;
}
public TreeNode getMin(TreeNode node){
while(node.left!=null){
node=node.left;
}
return node;
}
}
701. 二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
解题：
1.如果当前树为空，插入节点作为新节点
2.左子树
3.右子树
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null){
TreeNode buildNode=new TreeNode(val);
return buildNode;
}
if(root.val>val){
root.left= insertIntoBST(root.left,val);
}
if(root.val<val){
root.right= insertIntoBST(root.right,val);
}
return root;
}
}
700. 二叉搜索树中的搜索
难度简单
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
1.如果节点不存在，则返回 NULL。
2.返回左子树
3.返回右子树
3.返回根节点
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root==null){
return null;
}
if(val==root.val){
return root;
}
if(val<root.val){
root.left=searchBST(root.left,val);
return root.left;
}
if(val>root.val){
root.right=searchBST(root.right,val);
return root.right;
}
return root;
}
}
98. 验证二叉搜索树
难度中等1129
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
这里是有坑的哦，我们按照刚才的思路，每个节点自己要做的事不就是比较自己和左右孩子吗？看起来应该这样写代码：
boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (root.left != null && root.val <= root.left.val)
return false;
if (root.right != null && root.val >= root.right.val)
return false;
return isValidBST(root.left)
&& isValidBST(root.right);
}
但是这个算法出现了错误，BST 的每个节点应该要小于右边子树的所有节点，下面这个二叉树显然不是 BST，因为节点 10 的右子树中有一个节点 6，但是我们的算法会把它判定为合法 BST：
出现问题的原因在于，对于每一个节点 root，代码值检查了它的左右孩子节点是否符合左小右大的原则；但是根据 BST 的定义，root 的整个左子树都要小于 root.val，整个右子树都要大于 root.val。
问题是，对于某一个节点 root，他只能管得了自己的左右子节点，怎么把 root 的约束传递给左右子树呢？
class Solution {
public boolean isValidBST(TreeNode root) {
return build(root,null,null);
}
public boolean build(TreeNode root,TreeNode min,TreeNode max){
if(root==null){
return true;
}
if(min!=null && root.val<=min.val){
return false;
}
if(max!=null && root.val>=max.val ){
return false;
}
return build(root.left,min,root)&&build(root.right,root,max);
}
}
1.min!=null && root.val<=min.val 先判断非空
2.max!=null && root.val>=max.val 先判断非空
3.build(root.left,min,root)&&build(root.right,root,max); 左中右
我们通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点，这也是二叉树算法的一个小技巧吧。
96. 不同的二叉搜索树
难度中等
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
class Solution {
public int numTrees(int n) {
return num(1,n);
}
public int num(int low,int hight){
if(low>hight){
return 1;
}
int count=0;
for(int i=low;i<=hight;i++){
int left=num(low,i-1);
int rigth=num(i+1,hight);
count+=(left*rigth);
}
return count;
}
}
很遗憾，超时了
使用备忘录
class Solution {
int memory[][];
public int numTrees(int n) {
memory=new int[n+1][n+1];
return num(1,n);
}
public int num(int low,int hight){
if(low>hight){
return 1;
}
if(memory[low][hight]!=0){
return memory[low][hight];
}
int count=0;
for(int i=low;i<=hight;i++){
int left=num(low,i-1);
int rigth=num(i+1,hight);
count+=(left*rigth);
}
memory[low][hight]=count;
return count;
}
}
若有收获，就点个赞吧
0 人点赞
