递归三部曲！！！
- 确定递归函数的参数和返回值
- 确定终止条件
- 确定单层递归的逻辑
模板题
226. 翻转二叉树 - 力扣（LeetCode）
/*** 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 {//1 确定递归函数和返回值public TreeNode invertTree(TreeNode root) {//2 确定终止条件if(root == null){return null;}//3 确定单层递归逻辑 交换左右孩子swap(root);invertTree(root.left);invertTree(root.right);return root;}//交换函数void swap(TreeNode root){TreeNode temp = root.left;root.left = root.right;root.right = temp;}
}模板
递归模板
前序遍历
144. 二叉树的前序遍历 - 力扣（LeetCode）
import java.util.List;
import java.util.ArrayList;/*** 定义二叉树节点类*/
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 {/*** 用于存储前序遍历的结果*/List<Integer> ret = new ArrayList<>();/*** 前序遍历二叉树，并返回遍历的结果* @param root 二叉树的根节点* @return 返回前序遍历的节点值列表*/public List<Integer> preorderTraversal(TreeNode root) {Demo(root); // 调用递归方法进行前序遍历return ret; // 返回遍历结果}/*** 递归方法进行前序遍历* @param root 当前遍历到的节点*/void Demo(TreeNode root){if(root == null){ // 如果当前节点为空，返回return;}ret.add(root.val); // 将当前节点的值添加到结果列表中Demo(root.left); // 递归遍历左子树Demo(root.right); // 递归遍历右子树}
}后序遍历
145. 二叉树的后序遍历 - 力扣（LeetCode）
import java.util.List;
import java.util.ArrayList;/*** 定义二叉树节点类*/
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 {/*** 用于存储后序遍历的结果*/List<Integer> ret = new ArrayList<>();/*** 后序遍历二叉树，并返回遍历的结果* @param root 二叉树的根节点* @return 返回后序遍历的节点值列表*/public List<Integer> postorderTraversal(TreeNode root) {Demo(root); // 调用递归方法进行后序遍历return ret; // 返回遍历结果}/*** 递归方法进行后序遍历* @param root 当前遍历到的节点*/void Demo(TreeNode root){if(root == null){ // 如果当前节点为空，返回return;}Demo(root.left); // 递归遍历左子树Demo(root.right); // 递归遍历右子树ret.add(root.val); // 将当前节点的值添加到结果列表中}
}中序遍历
94. 二叉树的中序遍历 - 力扣（LeetCode）
import java.util.List;
import java.util.ArrayList;/*** 定义二叉树节点类*/
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 {/*** 用于存储中序遍历的结果*/List<Integer> ret = new ArrayList<>();/*** 中序遍历二叉树，并返回遍历的结果* @param root 二叉树的根节点* @return 返回中序遍历的节点值列表*/public List<Integer> inorderTraversal(TreeNode root) {Demo(root); // 调用递归方法进行中序遍历return ret; // 返回遍历结果}/*** 递归方法进行中序遍历* @param root 当前遍历到的节点*/void Demo(TreeNode root){if(root == null){ // 如果当前节点为空，返回return;}Demo(root.left); // 递归遍历左子树ret.add(root.val); // 将当前节点的值添加到结果列表中Demo(root.right); // 递归遍历右子树}
}迭代版本
前序遍历
144. 二叉树的前序遍历 - 力扣（LeetCode）
import java.util.List;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Deque;/*** 定义二叉树节点类*/
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 {/*** 前序遍历二叉树，并返回遍历的结果* @param root 二叉树的根节点* @return 返回前序遍历的节点值列表*/public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>(); // 创建一个列表用于存储遍历结果if(root == null){ // 如果根节点为空，则直接返回空列表return ret;}Deque<TreeNode> deque = new ArrayDeque<>(); // 创建一个双端队列用于存储待访问的节点deque.addFirst(root); // 将根节点添加到队列的前端while(!deque.isEmpty()){ // 当队列不为空时，进行循环TreeNode node = deque.removeFirst(); // 从队列前端移除一个节点ret.add(node.val); // 将节点的值添加到结果列表中// 如果节点的右子节点不为空，则将其添加到队列的前端if(node.right != null){deque.addFirst(node.right);}// 如果节点的左子节点不为空，则将其添加到队列的前端if(node.left != null){deque.addFirst(node.left);}}return ret; // 返回遍历结果}
}后序遍历
import java.util.List;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Collections;/*** 定义二叉树节点类*/
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 {/*** 后序遍历二叉树，并返回遍历的结果* @param root 二叉树的根节点* @return 返回后序遍历的节点值列表*/public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>(); // 创建一个列表用于存储遍历结果if(root == null){ // 如果根节点为空，则直接返回空列表return ret;}Deque<TreeNode> deque = new ArrayDeque<>(); // 创建一个双端队列用于存储待访问的节点deque.add(root); // 将根节点添加到队列的后端while(!deque.isEmpty()){ // 当队列不为空时，进行循环TreeNode node = deque.removeFirst(); // 从队列后端移除一个节点ret.add(node.val); // 将节点的值添加到结果列表中// 如果节点的左子节点不为空，则将其添加到队列的前端if(node.left != null){deque.addFirst(node.left);}// 如果节点的右子节点不为空，则将其添加到队列的前端if(node.right != null){deque.addFirst(node.right);}}// 后序遍历的结果是左-右-根，而我们添加到列表的顺序是根-左-右，所以需要反转列表Collections.reverse(ret);return ret; // 返回遍历结果}
}中序遍历
94. 二叉树的中序遍历 - 力扣（LeetCode）
import java.util.List;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Deque;/*** 定义二叉树节点类*/
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 {/*** 中序遍历二叉树，并返回遍历的结果* @param root 二叉树的根节点* @return 返回中序遍历的节点值列表*/public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>(); // 创建一个列表用于存储遍历结果if(root == null){ // 如果根节点为空，则直接返回空列表return ret;}Deque<TreeNode> deque = new ArrayDeque<>(); // 创建一个双端队列用于存储待访问的节点TreeNode cur = root; // 初始化当前节点为根节点// 使用循环进行遍历，直到当前节点为空且队列为空while(cur != null || !deque.isEmpty()){// 如果当前节点不为空，则将当前节点及其所有左子节点加入队列if(cur != null){deque.addFirst(cur); // 将当前节点加入队列前端cur = cur.left; // 移动到当前节点的左子节点}else{// 如果当前节点为空，则从队列中取出一个节点cur = deque.removeFirst(); // 从队列前端移除一个节点ret.add(cur.val); // 将节点的值添加到结果列表中cur = cur.right; // 移动到当前节点的右子节点}}return ret; // 返回遍历结果}
}层序遍历
102. 二叉树的层序遍历 - 力扣（LeetCode）
import java.util.ArrayList;
import java.util.List;
import java.util.ArrayDeque;/*** 定义一个二叉树的节点*/
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;}
}/*** 解决方案类，包含 levelOrder 方法来遍历二叉树*/
class Solution {/*** 该方法执行二叉树的层序遍历（广度优先搜索）。** @param root 要遍历的二叉树的根节点* @return 一个列表的列表，其中每个子列表包含特定层级的节点值*/public List<List<Integer>> levelOrder(TreeNode root) {// 初始化一个空列表来存储结果List<List<Integer>> ret = new ArrayList<>();// 如果根节点为空，返回一个空列表，因为没有节点可以遍历if (root == null) {return ret;}// 创建一个双端队列来保存每一层的节点ArrayDeque<TreeNode> deque = new ArrayDeque<>();// 将根节点添加到双端队列中deque.addFirst(root);// 继续遍历直到双端队列为空while (!deque.isEmpty()) {// 创建一个列表来存储当前层级的节点值ArrayList<Integer> list = new ArrayList<>();// 遍历当前层级的节点for (int i = deque.size(); i > 0; i--) {// 从双端队列中移除最后一个节点（因为我们是从右到左处理）TreeNode cur = deque.removeLast();// 将当前节点的值添加到列表中list.add(cur.val);// 如果当前节点有左子节点，将其添加到双端队列的前端if (cur.left != null) {deque.addFirst(cur.left);}// 如果当前节点有右子节点，将其添加到双端队列的前端if (cur.right != null) {deque.addFirst(cur.right);}}// 将当前层级的值列表添加到结果列表中ret.add(list);}// 返回包含每层节点值的结果列表return ret;}
}层序遍历相关题目
二叉树的右视图
199. 二叉树的右视图 - 力扣（LeetCode）
import java.util.ArrayList;
import java.util.List;
import java.util.ArrayDeque;/*** 定义一个二叉树的节点*/
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;}
}/*** 解决方案类，包含 rightSideView 方法来获取二叉树右侧视图*/
class Solution {/*** 该方法获取二叉树的右侧视图。** @param root 要获取右侧视图的二叉树的根节点* @return 一个列表，包含从根节点到每一层最右边的节点值*/public List<Integer> rightSideView(TreeNode root) {// 初始化一个空列表来存储结果List<Integer> ret = new ArrayList<>();// 如果根节点为空，返回空列表if (root == null) {return ret;}// 创建一个双端队列来保存每一层的节点ArrayDeque<TreeNode> deque = new ArrayDeque<>();// 将根节点添加到双端队列的前端deque.addFirst(root);// 当双端队列不为空时，继续遍历while (!deque.isEmpty()) {// 获取当前层的节点数量int levelSize = deque.size();// 用于记录当前层是否已经处理到最后一个节点int count = 0;// 遍历当前层的所有节点for (int i = 0; i < levelSize; i++) {// 从双端队列的前端移除节点TreeNode cur = deque.removeFirst();// 每处理完一层的最后一个节点，就将其值添加到结果列表中if (i == levelSize - 1) {ret.add(cur.val);}// 如果当前节点有左子节点，将其添加到双端队列的前端if (cur.left != null) {deque.addLast(cur.left);}// 如果当前节点有右子节点，将其添加到双端队列的前端if (cur.right != null) {deque.addLast(cur.right);}// 每处理一个节点，计数器加一count++;}}// 返回包含每层最右边节点值的结果列表return ret;}
}二叉树的层平均值
637. 二叉树的层平均值 - 力扣（LeetCode）
import java.util.ArrayList;
import java.util.List;
import java.util.Deque;
import java.util.ArrayDeque;/*** 定义一个二叉树的节点*/
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;}
}/*** 解决方案类，包含 averageOfLevels 方法来计算二叉树每一层的平均值*/
class Solution {/*** 该方法计算二叉树每一层的平均值。** @param root 要计算每层平均值的二叉树的根节点* @return 一个列表，包含每一层的平均值*/public List<Double> averageOfLevels(TreeNode root) {// 初始化一个空列表来存储每层的平均值List<Double> ret = new ArrayList<>();// 如果根节点为空，返回空列表if (root == null) {return ret;}// 创建一个双端队列来保存每一层的节点Deque<TreeNode> arrayDeque = new ArrayDeque<>();// 将根节点添加到双端队列的前端arrayDeque.addFirst(root);// 当双端队列不为空时，继续遍历while (!arrayDeque.isEmpty()) {// 初始化当前层的节点值总和double sum = 0.0;// 获取当前层的节点数量int m = arrayDeque.size();// 遍历当前层的所有节点for (int i = arrayDeque.size(); i > 0; i--) {// 从双端队列的后端移除节点TreeNode cur = arrayDeque.removeLast();// 将当前节点的值累加到总和中sum += cur.val;// 如果当前节点有左子节点，将其添加到双端队列的前端if (cur.left != null) {arrayDeque.addFirst(cur.left);}// 如果当前节点有右子节点，将其添加到双端队列的前端if (cur.right != null) {arrayDeque.addFirst(cur.right);}}// 将当前层的平均值添加到结果列表中ret.add(sum / m);}// 返回包含每层平均值的结果列表return ret;}
}N叉树的层序遍历
429. N 叉树的层序遍历 - 力扣（LeetCode）
import java.util.ArrayList;
import java.util.List;
import java.util.ArrayDeque;
import java.util.Deque;/*** 定义一个树节点*/
class Node {public int val; // 节点的值public List<Node> children; // 子节点列表// 构造函数public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
}/*** 解决方案类，包含 levelOrder 方法来对树进行层序遍历*/
class Solution {/*** 该方法对树进行层序遍历，并返回每一层的节点值。** @param root 树的根节点* @return 一个列表的列表，其中每个子列表包含每一层的节点值*/public List<List<Integer>> levelOrder(Node root) {// 初始化一个空列表来存储层序遍历的结果List<List<Integer>> ret = new ArrayList<>();// 如果根节点为空，返回空列表if (root == null) {return ret;}// 创建一个双端队列来存储每一层的节点Deque<Node> deque = new ArrayDeque<>();// 将根节点添加到双端队列的前端deque.addFirst(root);// 当双端队列不为空时，继续遍历while (!deque.isEmpty()) {// 创建一个列表来存储当前层的节点值ArrayList<Integer> list = new ArrayList<>();// 获取当前层的节点数量for (int i = deque.size(); i > 0; i--) {// 从双端队列的后端移除节点Node cur = deque.removeLast();// 将当前节点的值添加到当前层的列表中list.add(cur.val);// 获取当前节点的子节点列表List<Node> childs = cur.children;// 遍历子节点列表for (int j = 0; j < childs.size(); j++) {// 将子节点添加到双端队列的前端，以便下一轮遍历deque.addFirst(childs.get(j));}}// 将当前层的节点值列表添加到结果列表中ret.add(list);}// 返回包含每层节点值的结果列表return ret;}
}在每个树行中找最大值
515. 在每个树行中找最大值 - 力扣（LeetCode）
import java.util.ArrayList;
import java.util.List;
import java.util.ArrayDeque;/*** 定义一个二叉树节点。*/
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 {/*** 这个方法找出二叉树每一级的最大值，并将它们作为一个列表返回。** @param root 二叉树的根节点。* @return 一个整数列表，其中每个整数是二叉树某一级别的最大值。*/public List<Integer> largestValues(TreeNode root) {// 初始化一个空列表来存储每一级的最大值。List<Integer> ret = new ArrayList<>();// 如果根节点为空，返回一个空列表，因为树中没有值。if(root == null){return ret;}// 创建一个双端队列来保存二叉树的节点。// 这将用于执行二叉树的层序遍历。ArrayDeque<TreeNode> deque = new ArrayDeque<>();// 将根节点添加到双端队列中。deque.add(root);// 继续循环直到双端队列为空，这意味着所有层级都已处理。while(!deque.isEmpty()){// 初始化当前层的最大值为最小可能的整数。int max = Integer.MIN_VALUE;// 遍历当前层的所有节点。// 循环从双端队列的大小开始，递减到1。// 这是因为我们使用的是双端队列，并且节点被添加到队列的前端以供下一层使用。for(int i = deque.size(); i > 0; i--){// 移除双端队列中最后添加的节点（当前层的第一个节点）。TreeNode cur = deque.removeLast();// 如果当前节点的值大于当前层的最大值，则更新最大值。max = Math.max(max, cur.val);// 如果当前节点有左子节点，将其添加到双端队列的前端。if(cur.left != null){deque.addFirst(cur.left);}// 如果当前节点有右子节点，将其添加到双端队列的前端。if(cur.right != null){deque.addFirst(cur.right);}}// 在处理完当前层的所有节点后，将最大值添加到结果列表中。ret.add(max);}// 返回每个层级的最大值列表。return ret;}
}填充每个节点的下一个右侧节点指针
116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）
import java.util.ArrayDeque;
import java.util.Queue;class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
}class Solution {public Node connect(Node root) {// 如果根节点为空，直接返回nullif (root == null) {return null;}// 使用双端队列来存储每一层的节点Queue<Node> deque = new ArrayDeque<>();// 将根节点添加到队列的开头deque.addFirst(root);// 循环直到队列中的所有节点都被处理while (!deque.isEmpty()) {// 获取当前层的节点数量int size = deque.size();// 初始化前一个节点为nullNode pre = null;// 遍历当前层的所有节点for (int i = 0; i < size; i++) {// 从队列的末尾移除节点（因为添加子节点时是在队列的开头添加，所以这里从末尾移除）Node cur = deque.removeLast();// 如果前一个节点不为空，将前一个节点的next指向当前节点if (pre != null) {pre.next = cur;} else {// 如果前一个节点为空，说明当前节点是当前层的第一个节点，不需要设置next// 但是需要更新pre为当前节点，以便后续节点的next可以正确设置pre = cur;}// 如果当前节点有左子节点，将其添加到队列的开头if (cur.left != null) {deque.addFirst(cur.left);}// 如果当前节点有右子节点，将其添加到队列的开头if (cur.right != null) {deque.addFirst(cur.right);}// 更新pre为当前节点，以便下一次循环时可以正确设置下一个节点的nextpre = cur;}// 在每一层的末尾，将前一个节点的next设置为null，因为这是该层的最后一个节点pre.next = null;}// 返回根节点return root;}
}二叉树的最大深度
104. 二叉树的最大深度 - 力扣（LeetCode）
/*** 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 {/*** 计算二叉树的最大深度。* @param root 二叉树的根节点* @return 二叉树的最大深度*/public int maxDepth(TreeNode root) {// 如果根节点为空，返回0，表示树为空，深度为0if(root == null){return 0;}// 初始化最大深度为0int max = 0;// 声明当前节点变量TreeNode cur;// 使用双端队列来存储待处理的节点ArrayDeque<TreeNode> deque = new ArrayDeque<>();// 将根节点加入队列deque.addFirst(root);// 当队列不为空时，继续处理while(!deque.isEmpty()){// 遍历当前层的所有节点for(int i = deque.size(); i > 0; i--){// 取出队列中的最后一个节点cur = deque.removeLast();// 如果当前节点的左子节点不为空，将其加入队列的前端if(cur.left != null){deque.addFirst(cur.left);}// 如果当前节点的右子节点不为空，将其加入队列的前端if(cur.right != null){deque.addFirst(cur.right);}}// 每处理完一层，深度加1max++;}// 返回最大深度return max;}
}二叉树的最小深度
111. 二叉树的最小深度 - 力扣（LeetCode）
/*** 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 {/*** 计算二叉树的最小深度。* @param root 二叉树的根节点* @return 二叉树的最小深度*/public int minDepth(TreeNode root) {// 如果根节点为空，返回0，表示树为空，深度为0if(root == null){return 0;}// 初始化深度为0int depth = 0;// 声明当前节点变量TreeNode cur;// 使用双端队列来存储待处理的节点ArrayDeque<TreeNode> deque = new ArrayDeque<>();// 将根节点加入队列deque.addFirst(root);// 当队列不为空时，继续处理while(!deque.isEmpty()){// 每处理完一层，深度加1depth++;// 遍历当前层的所有节点for(int i = deque.size(); i > 0; i--){// 取出队列中的最后一个节点cur = deque.removeLast();// 如果当前节点的左子节点不为空，将其加入队列的前端if(cur.left != null){deque.addFirst(cur.left);}// 如果当前节点的右子节点不为空，将其加入队列的前端if(cur.right != null){deque.addFirst(cur.right);}// 如果当前节点是叶子节点（没有左右子节点），则返回当前深度if(cur.left == null && cur.right == null){return depth;}}}// 如果遍历完所有节点都没有找到叶子节点，返回深度（这种情况在非完全二叉树中可能出现）return depth;}
}找树左下角的值
513. 找树左下角的值 - 力扣（LeetCode）
class Solution {/*** 找到二叉树中左下角的值。* @param root 二叉树的根节点* @return 二叉树左下角的值*/public int findBottomLeftValue(TreeNode root) {// 如果根节点为空，返回0if(root == null){return 0;}// 使用队列来实现层次遍历Deque<TreeNode> list = new LinkedList<>();list.addLast(root); // 将根节点加入队列TreeNode cur; // 用于存储当前节点int ret = 0; // 用于存储左下角的值// 循环直到队列为空while(true){int size = list.size(); // 获取当前层的节点数for(int i = 0; i < size; i++){cur = list.removeFirst(); // 从队列头部移除一个节点，并存储在cur中// 如果是当前层的第一个节点，更新ret为当前节点的值if(i == 0){ret = cur.val;}// 如果当前节点有左子节点，加入队列if(cur.left != null) {list.addLast(cur.left);}// 如果当前节点有右子节点，加入队列if(cur.right != null) {list.addLast(cur.right);}}// 如果队列为空，说明已经到达了最后一层，返回retif(list.isEmpty()){return ret;}}}
}
后序遍历相关题目
对称二叉树
101. 对称二叉树 - 力扣（LeetCode）
/*** 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 boolean isSymmetric(TreeNode root) {// 调用递归函数compare来比较root的左右子树是否对称return compare(root.left, root.right);}// 1 确定递归函数boolean compare(TreeNode left, TreeNode right){// 2 确定终止条件// 如果左子树为空，右子树不为空，或者左子树不为空，右子树为空，返回falseif(left == null && right != null){return false;}if(left != null && right == null){return false;}// 如果左右子树都为空，说明这两个节点对称，返回trueif(left == null && right == null){return true;}// 如果左右子树的值不相等，说明这两个节点不对称，返回falseif(left.val != right.val){return false;}// 3 处理单步递归逻辑// 递归比较左子树的左子节点和右子树的右子节点是否对称boolean leftSame = compare(left.left, right.right);// 递归比较左子树的右子节点和右子树的左子节点是否对称boolean rightSame = compare(left.right, right.left);// 如果两个递归调用都返回true，则说明当前节点的左右子树对称，返回truereturn leftSame && rightSame;}
}平衡二叉树
110. 平衡二叉树 - 力扣（LeetCode）
class Solution {public boolean isBalanced(TreeNode root) {int ret = Demo(root); // 调用递归函数，获取树的高度if(ret == -1){ // 检查返回值是否为-1，表示不平衡return false; // 如果不平衡，返回false}else{return true; // 如果平衡，返回true}}// 1 确定递归函数及返回值int Demo(TreeNode node){// 2 确定终止条件if(node == null){return 0; // 空节点高度为0}// 3 单步递归逻辑int leftHeight = Demo(node.left); // 递归计算左子树的高度if(leftHeight == -1){ // 如果左子树不平衡return -1; // 直接返回-1}int rightHeight = Demo(node.right); // 递归计算右子树的高度if(rightHeight == -1){ // 如果右子树不平衡return -1; // 直接返回-1}// 检查当前节点的左右子树高度差if(Math.abs(rightHeight - leftHeight) > 1){ // 如果高度差大于1return -1; // 返回-1，表示不平衡}else{// 返回当前节点的高度return Math.max(rightHeight, leftHeight) + 1; // 当前节点的高度为左右子树最大高度加1}}
}
左叶子之和
404. 左叶子之和 - 力扣（LeetCode）
class Solution {/*** 计算给定二叉树中所有左叶子节点的值之和。* @param root 二叉树的根节点。* @return 所有左叶子节点的值之和。*/public int sumOfLeftLeaves(TreeNode root) {// 如果根节点为空，返回0，因为空树没有叶子节点。if(root == null){return 0;}// 递归计算左子树中所有左叶子节点的值之和。int leftSum = sumOfLeftLeaves(root.left);// 递归计算右子树中所有左叶子节点的值之和。int rightSum = sumOfLeftLeaves(root.right);// 初始化中间变量midValue，用于存储当前节点左叶子节点的值。int midValue = 0;// 如果当前节点的左子节点不为空，且左子节点没有子节点（即左子节点是叶子节点），// 则将当前节点的左子节点的值赋给midValue。if(root.left != null && root.left.left == null && root.left.right == null){midValue = root.left.val;}// 计算总和，包括左子树、右子树中左叶子节点的值之和，以及当前节点的左叶子节点的值（如果有）。int sum = leftSum + rightSum + midValue;// 返回所有左叶子节点的值之和。return sum;}
}二叉树的最近公共祖先
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
/*** Definition for a binary tree node.* 定义二叉树节点*/
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}class Solution {/*** Find the lowest common ancestor of two nodes in a binary tree.* 在二叉树中找到两个节点的最低公共祖先* @param root the root of the binary tree* @param p one of the nodes* @param q the other node* @return the lowest common ancestor of p and q*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 如果根节点为空，直接返回nullif(root == null){return root;}// 如果根节点是p或q，那么它就是最低公共祖先if(root == p || root == q){return root;}// 在左子树中递归查找最低公共祖先TreeNode leftStatus = lowestCommonAncestor(root.left, p, q);// 在右子树中递归查找最低公共祖先TreeNode rightStatus = lowestCommonAncestor(root.right, p, q);// 如果左右子树都找到了节点，说明p和q在root的两侧，root就是最低公共祖先if(leftStatus != null && rightStatus != null){return root;}// 如果只在左子树中找到节点，说明p和q都在左子树中，返回左子树中找到的节点// 同理，如果只在右子树中找到节点，返回右子树中找到的节点else if(leftStatus != null && rightStatus == null){return leftStatus;}else if(leftStatus == null && rightStatus != null){return rightStatus;// 如果左右子树都没有找到节点，说明p和q都不在以root为根的子树中，返回null}else{return null;}}
}前序遍历相关题目
二叉树的所有路径
257. 二叉树的所有路径 - 力扣（LeetCode）
/*** Definition for a binary tree node.* 定义二叉树节点，包含整数值val，左子节点left，和右子节点right。* 包含三个构造函数，分别用于创建空节点、只有值的节点、以及具有值和左右子节点的节点。* 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 {// 使用两个列表，一个用于存储当前路径的节点值，一个用于存储所有路径的字符串表示。List<Integer> list = new ArrayList<>();List<String> ret = new ArrayList<>();/*** 计算给定二叉树的所有路径。* @param root 二叉树的根节点。* @return 包含所有路径的字符串列表。*/public List<String> binaryTreePaths(TreeNode root) {// 如果根节点为空，直接返回空的路径列表。if(root == null){return ret;}// 调用递归函数来填充路径列表。Demo(root);// 返回包含所有路径的列表。return ret;}/*** 递归函数，用于遍历二叉树并记录所有路径。* @param node 当前遍历到的节点。*/void Demo(TreeNode node){// 如果节点为空，结束递归。if(node == null){return;}// 将当前节点的值添加到路径列表中。list.add(node.val);// 如果当前节点是一个叶子节点（没有子节点），则将路径添加到结果列表中。if(node.left == null && node.right == null){StringBuilder sb = new StringBuilder();for(int i = 0; i < list.size() - 1; i++){sb.append(list.get(i) + "->");}sb.append(list.get(list.size() - 1));ret.add(sb.toString());}// 递归访问左子节点，并且在返回之前从路径列表中移除当前节点的值。if(node.left != null){Demo(node.left);list.remove(list.size() - 1);}// 递归访问右子节点，并且在返回之前从路径列表中移除当前节点的值。if(node.right != null){Demo(node.right);list.remove(list.size() - 1);}}
}路径总和
112. 路径总和 - 力扣（LeetCode）
// 定义一个二叉树节点的类
class TreeNode {int val; // 节点的值TreeNode left; // 指向左子节点的引用TreeNode right; // 指向右子节点的引用// 构造函数，初始化节点的值和左右子节点TreeNode(int x) {val = x;}
}// 定义一个解法类
class Solution {// 方法：判断是否存在一条路径，使得路径上所有节点的值之和等于目标和public boolean hasPathSum(TreeNode root, int targetSum) {// 如果根节点为空，返回false，因为没有路径if (root == null) {return false;}// 从目标和中减去当前节点的值targetSum -= root.val;// 如果当前节点是叶节点（没有左右子节点），判断目标和是否为0// 如果为0，说明当前路径的和等于目标和，返回trueif (root.left == null && root.right == null) {return targetSum == 0;}// 如果当前节点有左子节点，递归调用hasPathSum方法检查左子树if (root.left != null) {boolean leftSum = hasPathSum(root.left, targetSum);// 如果左子树中存在符合条件的路径，返回trueif (leftSum) {return true;}}// 如果当前节点有右子节点，递归调用hasPathSum方法检查右子树if (root.right != null) {boolean rightSum = hasPathSum(root.right, targetSum);// 如果右子树中存在符合条件的路径，返回trueif (rightSum) {return true;}}// 如果当前节点的左右子树中都没有符合条件的路径，返回falsereturn false;}
}其他类题型
按照一定规则构建二叉树
从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
/*** 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 {Map<Integer, Integer> map; // 用于存储中序遍历中每个节点值对应的索引public TreeNode buildTree(int[] inorder, int[] postorder) {map = new HashMap<>(); // 初始化哈希表for(int i = 0; i < inorder.length; i++){ // 填充哈希表map.put(inorder[i], i);}return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length); // 调用递归函数构建树}TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd){// 如果当前子树的范围无效，则返回nullif(inBegin >= inEnd || postBegin >= postEnd){return null;}// 获取后序遍历中最后一个元素，即当前子树的根节点int rootValue = postorder[postEnd - 1];// 获取根节点在中序遍历中的索引int rootIndex = map.get(rootValue);// 计算左子树的长度int leftLen = rootIndex - inBegin;// 创建当前子树的根节点TreeNode root = new TreeNode(rootValue);// 递归构建左子树root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + leftLen);// 递归构建右子树root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + leftLen, postEnd - 1);// 返回当前子树的根节点return root;}
}从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
/*** 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 {Map<Integer, Integer> map; // 用于存储中序遍历中每个节点值对应的索引/*** 根据给定的前序遍历和中序遍历数组构建二叉树。* @param preorder 前序遍历数组* @param inorder 中序遍历数组* @return 构建的二叉树的根节点*/public TreeNode buildTree(int[] preorder, int[] inorder) {map = new HashMap<>(); // 初始化哈希表for(int i = 0; i < inorder.length; i++){ // 填充哈希表map.put(inorder[i], i);}return findNode(preorder, 0, preorder.length, inorder, 0, inorder.length); // 调用递归函数构建树}/*** 递归函数，用于构建二叉树。* @param preorder 前序遍历数组* @param preBegin 前序遍历的开始索引* @param preEnd 前序遍历的结束索引* @param inorder 中序遍历数组* @param inBegin 中序遍历的开始索引* @param inEnd 中序遍历的结束索引* @return 当前子树的根节点*/TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd){// 如果当前子树的范围无效，则返回nullif(preBegin >= preEnd || inBegin >= inEnd){return null;}// 获取前序遍历中的第一个元素，即当前子树的根节点int rootValue = preorder[preBegin];// 获取根节点在中序遍历中的索引int rootIndex = map.get(rootValue);// 计算左子树的长度int leftLen = rootIndex - inBegin;// 创建当前子树的根节点TreeNode root = new TreeNode(rootValue);// 递归构建左子树// 注意这里的范围是 [preBegin + 1, preBegin + leftLen + 1)，因为前序遍历中根节点之后紧接着是左子树root.left = findNode(preorder, preBegin + 1, preBegin + leftLen + 1, inorder, inBegin, rootIndex);// 递归构建右子树// 右子树的开始索引是 preBegin + leftLen + 1，因为左子树之后是右子树root.right = findNode(preorder, preBegin + leftLen + 1, preEnd, inorder, rootIndex + 1, inEnd);// 返回当前子树的根节点return root;}
}最大二叉树
654. 最大二叉树 - 力扣（LeetCode）
/*** 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 {/*** 主函数，用于构建最大二叉树。* @param nums 整数数组，表示二叉树的节点值。* @return 构建的最大二叉树的根节点。*/public TreeNode constructMaximumBinaryTree(int[] nums) {// 如果数组为空或为null，则返回nullif (nums == null || nums.length == 0) {return null;}// 调用递归函数，从数组的开始到结束构建树return createTree(nums, 0, nums.length);}/*** 递归函数，用于构建最大二叉树。* @param nums 整数数组，表示二叉树的节点值。* @param begin 开始索引（包含）。* @param end 结束索引（不包含）。* @return 当前子树的根节点。*/TreeNode createTree(int[] nums, int begin, int end) {// 如果开始索引大于或等于结束索引，表示当前子树为空，返回nullif (begin >= end) {return null;}// 初始化根节点的值为最小整数，这样可以确保找到最大的值int rootValue = Integer.MIN_VALUE;// 初始化根节点的索引int rootIndex = 0;// 遍历当前子树的范围，找到最大的值及其索引for (int i = begin; i < end; i++) {if (rootValue < nums[i]) {rootValue = nums[i];rootIndex = i;}}// 创建当前子树的根节点TreeNode root = new TreeNode(rootValue);// 递归构建左子树，左子树的范围是开始索引到根节点索引root.left = createTree(nums, begin, rootIndex);// 递归构建右子树，右子树的范围是根节点索引的下一个到结束索引root.right = createTree(nums, rootIndex + 1, end);// 返回当前子树的根节点return root;}
}合并二叉树
617. 合并二叉树 - 力扣（LeetCode）
/*** 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 {/*** 主函数，用于合并两棵二叉树。* @param root1 第一棵树的根节点。* @param root2 第二棵树的根节点。* @return 合并后的二叉树的根节点。*/public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {// 调用递归函数合并两棵树return Demo(root1, root2);}/*** 递归函数，用于合并两棵二叉树。* 在合并过程中，对应位置的节点值相加，左子树和右子树分别合并。* @param root1 第一棵树的根节点。* @param root2 第二棵树的根节点。* @return 合并后的二叉树的根节点。*/TreeNode Demo(TreeNode root1, TreeNode root2) {// 如果第一棵树为空，且第二棵树不为空，返回第二棵树的根节点if (root1 == null && root2 != null) {return root2;}// 如果第一棵树不为空，且第二棵树为空，返回第一棵树的根节点if (root1 != null && root2 == null) {return root1;}// 如果两棵树都为空，返回nullif (root1 == null && root2 == null) {return null;}// 如果两棵树都不为空，创建一个新的根节点，其值为两个根节点值的和TreeNode root = new TreeNode(root1.val + root2.val);// 递归地合并左子树root.left = Demo(root1.left, root2.left);// 递归地合并右子树root.right = Demo(root1.right, root2.right);// 返回合并后的二叉树的根节点return root;}
}二叉搜索树相关题目
中序遍历二叉搜索树是从小到大的！！！
二叉搜索树中的搜索
700. 二叉搜索树中的搜索 - 力扣（LeetCode）
/*** 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 {/*** 在二叉搜索树中搜索给定的值。* @param root 二叉搜索树的根节点。* @param val 要搜索的值。* @return 搜索到的节点，如果未找到则返回null。*/public TreeNode searchBST(TreeNode root, int val) {// 如果根节点为空，说明树为空，返回nullif (root == null) {return null;}// 如果根节点的值大于要搜索的值，说明目标值在左子树中if (root.val > val) {return searchBST(root.left, val);}// 如果根节点的值小于要搜索的值，说明目标值在右子树中else if (root.val < val) {return searchBST(root.right, val);}// 如果根节点的值等于要搜索的值，说明已经找到目标节点else if (root.val == val) {return root;}// 如果以上条件都不满足，说明未找到目标值，返回nullreturn null;}
}验证二叉搜索树
中序遍历二叉搜索树是从小到大的！！！
98. 验证二叉搜索树 - 力扣（LeetCode）
/*** 定义一个二叉树节点。*/
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 {// 用于记录前一个遍历到的节点，以便在中序遍历中检查节点的顺序性。TreeNode preNode = null;/*** 验证以 root 为根的二叉树是否为有效的二叉搜索树。* @param root 二叉树的根节点* @return 如果是有效的二叉搜索树，返回 true；否则返回 false。*/public boolean isValidBST(TreeNode root) {// 如果当前节点为空，说明已经到达叶子节点的下一层，返回 true。if (root == null) {return true;}// 首先递归检查左子树是否为有效的二叉搜索树。boolean leftStatus = isValidBST(root.left);// 如果前一个节点不为空，并且当前节点的值小于等于前一个节点的值，// 说明树不是有效的二叉搜索树，返回 false。if (preNode != null && root.val <= preNode.val) {return false;}// 将当前节点设置为前一个节点，以供后续节点比较。preNode = root;// 递归检查右子树是否为有效的二叉搜索树。boolean rightStatus = isValidBST(root.right);// 如果左右子树都为有效的二叉搜索树，返回 true，否则返回 false。return rightStatus && leftStatus;}
}二叉搜索树的最小绝对差
530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）
/*** 定义一个二叉树节点。*/
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 {// 用于存储当前找到的最小差值，初始化为最大整数。int ret = Integer.MAX_VALUE;// 用于记录上一次访问的节点。TreeNode pre = null;/*** 计算以 root 为根的二叉树中任意两个值之间的最小差值。* @param root 二叉树的根节点* @return 最小差值*/public int getMinimumDifference(TreeNode root) {// 调用递归方法来遍历树并计算最小差值。Demo(root);// 返回计算出的最小差值。return ret;}/*** 递归方法，用于遍历二叉树并计算最小差值。* @param root 当前节点*/void Demo(TreeNode root) {if (root == null) {// 如果当前节点为空，直接返回。return;}// 首先递归遍历左子树。Demo(root.left);// 如果前一个节点不为空，计算当前节点与前一个节点的差值，并更新最小差值。if (pre != null) {ret = Math.min(ret, root.val - pre.val);}// 更新前一个节点为当前节点。pre = root;// 递归遍历右子树。Demo(root.right);}
}二叉搜索树中的众数
501. 二叉搜索树中的众数 - 力扣（LeetCode）
/*** 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 {// 用于存储出现次数最多的元素List<Integer> ret;// 当前节点出现的次数int count = 0;// 出现次数最多的节点的次数int maxCount = 0;// 前一个节点的引用，用于比较当前节点和前一个节点的值是否相同TreeNode pre;/*** 找出二叉树中出现次数最多的元素* @param root 二叉树的根节点* @return 出现次数最多的元素数组*/public int[] findMode(TreeNode root) {// 初始化返回列表ret = new ArrayList<Integer>();// 调用DFS方法遍历二叉树Demo(root);// 将结果列表转换为数组int result[] = new int[ret.size()];for(int i = 0; i < ret.size(); i++){result[i] = ret.get(i);}return result;}/*** 深度优先搜索方法，用于遍历二叉树并找出出现次数最多的元素* @param cur 当前节点*/void Demo(TreeNode cur){if(cur == null){// 如果当前节点为空，直接返回return;}// 先遍历左子树Demo(cur.left);// 如果前一个节点为空，或者当前节点的值和前一个节点的值相同，则增加计数if(pre == null){count = 1;}else if(pre.val == cur.val){count++;}else{// 如果当前节点的值和前一个节点的值不同，则重置计数count = 1;}// 更新前一个节点为当前节点pre = cur;// 如果当前节点的计数等于最大计数，则将当前节点的值添加到结果列表中if(count == maxCount){ret.add(cur.val);}// 如果当前节点的计数大于最大计数，则清空结果列表，并添加当前节点的值if(count > maxCount){ret.clear();ret.add(cur.val);// 更新最大计数maxCount = count;}// 遍历右子树Demo(cur.right);}
}二叉搜索树的最近公共祖先
235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
/*** Definition for a binary tree node.* 定义二叉树节点类。*/
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}/*** Solution class that contains the method to find the lowest common ancestor of two nodes in a binary tree.* 解决方案类，包含寻找二叉树中两个节点的最低公共祖先的方法。*/
class Solution {/*** This method finds the lowest common ancestor of two nodes p and q in a binary tree.* 此方法在二叉树中找到两个节点p和q的最低公共祖先。** @param root the root of the binary tree.* @param p one of the nodes to find the lowest common ancestor for.* @param q the other node to find the lowest common ancestor for.* @return the lowest common ancestor node.*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 如果根节点为空，则返回null。if(root == null){return null;}// 如果根节点的值大于p和q的值，说明p和q都在左子树。if(root.val > p.val && root.val > q.val){// 递归地在左子树中寻找最低公共祖先。TreeNode left = lowestCommonAncestor(root.left, p, q);// 如果在左子树中找到了最低公共祖先，则返回它。if(left != null){return left;}}// 如果根节点的值小于p和q的值，说明p和q都在右子树。if(root.val < p.val && root.val < q.val){// 递归地在右子树中寻找最低公共祖先。TreeNode right = lowestCommonAncestor(root.right, p, q);// 如果在右子树中找到了最低公共祖先，则返回它。if(right != null){return right;}}// 如果以上两种情况都不满足，说明p和q一个在左子树，一个在右子树，或者p和q中的一个就是根节点。// 在这种情况下，根节点就是p和q的最低公共祖先。return root;}
}二叉搜索树中的插入操作
701. 二叉搜索树中的插入操作 - 力扣（LeetCode）
/*** 定义一个二叉树节点。*/
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 {/*** 将值 val 插入到以 root 为根的二叉搜索树中。* @param root 二叉搜索树的根节点。* @param val 要插入的值。* @return 插入新值后的二叉搜索树的根节点。*/public TreeNode insertIntoBST(TreeNode root, int val) {// 如果根节点为空，说明树是空的，直接创建一个新节点作为树的根。if(root == null){return new TreeNode(val);}// 如果要插入的值小于当前节点的值，说明新节点应该在左子树中。if(root.val > val){// 递归地在左子树中插入新值。root.left = insertIntoBST(root.left, val);}// 如果要插入的值大于当前节点的值，说明新节点应该在右子树中。else if(root.val < val){// 递归地在右子树中插入新值。root.right = insertIntoBST(root.right, val);}// 如果要插入的值等于当前节点的值，二叉搜索树不允许有重复值，所以不进行任何操作。// 返回根节点，此时树可能已经更新（如果插入了新节点）。return root;}
}删除二叉搜索树中的节点
450. 删除二叉搜索树中的节点 - 力扣（LeetCode）
/*** 实现在二叉搜索树中删除一个节点的操作。*/
public class Solution {/*** 在以 root 为根的二叉搜索树中删除值为 key 的节点。* @param root 二叉搜索树的根节点。* @param key 要删除的节点的值。* @return 删除节点后的二叉搜索树的根节点。*/public TreeNode deleteNode(TreeNode root, int key) {// 如果根节点为空，说明没有找到要删除的节点，直接返回null。if(root == null){return null;}// 如果当前节点的值等于要删除的值，需要进行删除操作。if(root.val == key){// 如果当前节点没有左右孩子，直接返回null，表示删除该节点。if(root.left == null && root.right == null){return null;}// 如果当前节点只有右孩子，返回右孩子，替代当前节点。else if(root.left == null && root.right != null){return root.right;}// 如果当前节点只有左孩子，返回左孩子，替代当前节点。else if(root.left != null && root.right == null){return root.left;}// 如果当前节点既有左孩子又有右孩子，找到右子树中最小的节点（最左下的节点），// 将其值复制到当前节点，然后递归地删除那个最小的节点。else{TreeNode cur = root.right;while(cur.left != null){cur = cur.left;}cur.left = root.left;root = root.right;return root;}}// 如果当前节点的值大于要删除的值，说明要删除的节点在左子树中，递归地在左子树中删除。if(root.val > key){root.left = deleteNode(root.left, key);}// 如果当前节点的值小于要删除的值，说明要删除的节点在右子树中，递归地在右子树中删除。if(root.val < key){root.right = deleteNode(root.right, key);}// 返回根节点，此时树可能已经更新（如果插入了新节点），或者当前节点不是要删除的值。return root;}
}修剪二叉搜索树
669. 修剪二叉搜索树 - 力扣（LeetCode）
class Solution {// 修剪二叉搜索树，使其只包含值在 [low, high] 范围内的节点public TreeNode trimBST(TreeNode root, int low, int high) {// 如果当前节点为空，直接返回 nullif(root == null){return root;}// 如果当前节点的值大于 high，则只需要考虑左子树if(root.val > high){// 递归修剪左子树return trimBST(root.left, low, high);}// 如果当前节点的值小于 low，则只需要考虑右子树if(root.val < low){// 递归修剪右子树return trimBST(root.right, low, high);}// 如果当前节点的值在 [low, high] 范围内，则保留该节点// 递归修剪左子树，确保左子树中的所有节点值也在 [low, high] 范围内root.left = trimBST(root.left, low, high);// 递归修剪右子树，确保右子树中的所有节点值也在 [low, high] 范围内root.right = trimBST(root.right, low, high);// 返回当前节点，此时当前节点及其子树已经满足条件return root;}
}将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return createTree(nums, 0, nums.length - 1);}// 使用左闭右闭区间 [left, right] 来构建子树private TreeNode createTree(int[] nums, int left, int right) {if (left > right) {return null;}// 计算中间索引，创建根节点int mid = left + (right - left) / 2;TreeNode root = new TreeNode(nums[mid]);// 递归构建左子树和右子树root.left = createTree(nums, left, mid - 1);root.right = createTree(nums, mid + 1, right);return root;}
}把二叉搜索树转换为累加树
1038. 从二叉搜索树到更大和树 - 力扣（LeetCode）
class Solution {// 用于存储当前节点的累计和int sum = 0;// 主函数，用于开始转换过程public TreeNode bstToGst(TreeNode root) {// 调用辅助函数进行转换Demo(root);// 返回转换后的树的根节点return root;}// 辅助函数，用于递归地转换树void Demo(TreeNode root) {// 基本情况：如果节点为空，直接返回if (root == null) {return;}// 先递归地处理右子树bstToGst(root.right);// 将当前节点的值加到累计和中sum += root.val;// 更新当前节点的值为累计和root.val = sum;// 再递归地处理左子树bstToGst(root.left);}
}
