25.二叉树中序遍历
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]示例 2：
输入：root = []
输出：[]示例 3：
输入：root = [1]
输出：[1]题解：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList();
inorder(root,res);
return res;
}
public void inorder(TreeNode root,List<Integer> res){
if(root == null){
return;
}
//这里灵活调整三行代码顺序就可以决定是前，中，后三种遍历顺序（前：将res.add(root.val)放到最前面，后：将res.add(root.val)放到最后面）
inorder(root.left,res);
res.add(root.val);
inorder(root.right,res);
}
}26二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3示例 2：
输入：root = [1,null,2]
输出：2题解：
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
else{
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight,rightHeight) + 1;
}
}
}27.翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]示例 2：
输入：root = [2,1,3]
输出：[2,3,1]示例 3：
输入：root = []
输出：[]题解：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}28.对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true题解：
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root.left,root.right);
}
public boolean check(TreeNode p,TreeNode q){
if(p == null && q== null){
return true;
}
if(p == null || q == null){
return false;
}
return p.val == q.val && check(p.left,q.right) && check(p.right,q.left);
}
}29.二叉树的半径
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。示例 2：
输入：root = [1,2]
输出：1核心思想：
找到左右子树深度之和最大值
题解：
class Solution {
int ans;
public int diameterOfBinaryTree(TreeNode root) {
ans = 1;
depth(root);
return ans - 1;
}
public int depth(TreeNode root){
if(root == null){
return 0;
}
int L = depth(root.left);
int R = depth(root.right);
ans = Math.max(ans,L + R + 1);
return Math.max(L,R) + 1;
}
}30.二叉树层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1]
输出：[[1]]示例 3：
输入：root = []
输出：[]核心思想：
使用队列来对存储处理每一个节点保证按顺序处理节点，其次通过队列当前有的元素来判断当前层数有几个节点要处理。
题解：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList();
if(root == null){
return ans;
}
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> level = new ArrayList();
int currentLevel = queue.size();
for(int i = 1; i <= currentLevel;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);
}
}
ans.add(level);
}
return ans;
}
}31.将有序数组转为二叉树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。这道题相对简单，方法有很多种，这里就以中序遍历的其中一种方式来做。
题解：
通过中序遍历，选择中间位置左边的数字作为根节点
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums,0,nums.length - 1);
}
public TreeNode helper(int[] nums,int left,int right){
if(left > right){
return null;
}
int mid = (left + right + 1) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums,left,mid - 1);
root.right = helper(nums,mid + 1,right);
return root;
}
}32.验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 严格小于 当前节点的数。
节点的右子树只包含 严格大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。题解：
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode node,long lower,long higher){
if(node == null){
return true;
}
if(node.val <= lower || node.val >= higher){
return false;
}
return isValidBST(node.left,lower,node.val) && isValidBST(node.right,node.val,higher);
}
}33.二叉搜索树查询倒数K个小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3题解：
这题主要结合二叉搜索树的特点，因为我们要找的是偏小的一边，所以我们优先搜索左子树，将左子树的节点塞到栈里面，然后再k次出栈就可以找到第k小的节点
class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
while(root != null || !stack.isEmpty()){
//优先搜索左子树
while(root != null){
stack.push(root);
root = root.left;
}
//出栈k次就能拿到第k小的节点
root = stack.pop();
--k;
//k==0则找到了直接中断
if(k == 0){
break;
}
//当最左端的左子树都找完没找到，那么就从子树节点的右子树节点开始，但后续搜索还是优先左子树搜索
root = root.right;
}
return root.val;
}
}34.二叉树右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
示例 2：
输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
解释：
示例 3：
输入：root = [1,null,3]
输出：[1,3]
示例 4：
输入：root = []
输出：[]
题解：
这题我们用层序遍历即可，只往res数组添加每层的最后一个节点值即可。
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ans = new ArrayList();
if(root == null){
return ans;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
while(size > 0){
TreeNode cur = queue.poll();
size--;
//只往结果数组添加最后一个元素，正常层序遍历没有这个if条件直接添加
if(size == 0){
ans.add(cur.val);
}
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
}
}
return ans;
}
}35.二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]示例 2：
输入：root = []
输出：[]示例 3：
输入：root = [0]
输出：[0]题解：
这题用先序遍历把节点存到list里面，然后通过遍历list访问节点来改变节点的指针，for循环 i 初始记得设为1
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList();
preorder(root,list);
int size = list.size();
//i索引指向当前子树的左节点，i-1就是根节点
for(int i = 1;i < size;i++){
TreeNode prev = list.get(i - 1), curr = list.get(i);
prev.left = null;
prev.right = curr;
}
}
public void preorder(TreeNode root,List<TreeNode> list){
if(root != null){
list.add(root);
preorder(root.left,list);
preorder(root.right,list);
}
}
}36.从先序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]题解：
做这题要先找到两个遍历的特性
前序遍历：根 → 左子树 → 右子树，所以
preorder[0]一定是整棵树的根。中序遍历：左子树 → 根 → 右子树，所以只要在中序数组中找到根的位置，就能把左、右子树的中序区间分开。
用一个指针 inorderIndex 指向中序遍历中「当前应该被匹配」的位置。
遍历前序数组 preorder，依次处理每个节点：
如果栈顶节点的值 ≠ inorder[inorderIndex]
说明当前前序节点是栈顶节点的左孩子。
因为前序是「根→左」，只要还没走到中序里的根，就一直在往左走。
于是
node.left = new TreeNode(preorderVal)，并压栈。
如果栈顶节点的值 == inorder[inorderIndex]
说明栈顶这个节点已经没有左子树了（中序里它的左边都处理完了）。
于是不断弹出栈顶，并让
inorderIndex++，直到栈顶节点不等于inorder[inorderIndex]或者栈空。此时最后弹出的那个节点，它的右孩子就是当前前序节点。
于是
node.right = new TreeNode(preorderVal)，并压栈。
把前序和中序对照看：
前序：
3, 9, 20, 15, 7中序：
9, 3, 15, 20, 7
过程模拟：
若
preorder为空，返回null。用
preorder[0]创建根节点root，压入栈。inorderIndex = 0。从
i = 1遍历preorder：取当前值
preorderVal，查看栈顶node。若
node.val != inorder[inorderIndex]：当前节点是
node的左孩子，创建并压栈。
否则：
不断弹出栈顶，同时
inorderIndex++，直到栈空或栈顶值不等于inorder[inorderIndex]。最后弹出的节点
node的右孩子就是当前节点，创建并压栈。
返回
root。
代码：
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || preorder.length == 0){
return null;
}
TreeNode root = new TreeNode(preorder[0]);
Deque<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
int inorderIndex = 0;
for(int i = 1;i < preorder.length;i++){
int preorderVal = preorder[i];
TreeNode node = stack.peek();
if(node.val != inorder[inorderIndex]){
node.left = new TreeNode(preorderVal);
stack.push(node.left);
} else{
while(!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]){
node = stack.pop();
inorderIndex++;
}
node.right = new TreeNode(preorderVal);
stack.push(node.right);
}
}
return root;
}
}37.路径总和
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3题解：
这题的要求其实很眼熟阿，在一个数据结构找到targetSum,对于这种问题我们可以使用前缀和，写起来简单还快。
class Solution {
public int pathSum(TreeNode root, int targetSum) {
Map<Long,Integer> prefix = new HashMap<Long,Integer>();
prefix.put(0L,1);
return dfs(root,prefix,0,targetSum);
}
public int dfs(TreeNode root,Map<Long,Integer> prefix,long curr,int targetSum){
if(root == null){
return 0;
}
int ret = 0;
curr += root.val;
ret = prefix.getOrDefault(curr - targetSum,0);
prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
ret += dfs(root.left,prefix,curr,targetSum);
ret += dfs(root.right,prefix,curr,targetSum);
prefix.put(curr,prefix.getOrDefault(curr,0) - 1);
return ret;
}
}38.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 。因为根据定义最近公共祖先节点可以为节点本身。示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1题解：
这题通过遍历二叉树存储父节点，用map存储，用子节点的值为key，父节点为值，这样就能通过子节点拿到父节点。再定义一个记录是否访问过的visited数组来做标记。
class Solution {
Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
Set<Integer> visited = new HashSet<Integer>();
public void dfs(TreeNode root){
if(root.left != null){
parent.put(root.left.val,root);
dfs(root.left);
}
if(root.right != null){
parent.put(root.right.val,root);
dfs(root.right);
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root);
while(p != null){
visited.add(p.val);
p = parent.get(p.val);
}
while(q != null){
if(visited.contains(q.val)){
return q;
}
q = parent.get(q.val);
}
return null;
}
}39二叉树路径和最大值
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42题解：
这道题在困难里面属于萝莉，简单通过递归计算每一个子树的路径和，然后通过max找最大就行了。注意树节点的值是可以为负数的，所以maxsum不能初始化为0，否则在max判断一直会是0.
class Solution {
//初始化为整形最小值防止负值的路径和
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
public int maxGain(TreeNode node){
if(node == null){
return 0;
}
int leftGain = Math.max(maxGain(node.left),0);
int rightGain = Math.max(maxGain(node.right),0);
int priceNewpath = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum,priceNewpath);
return node.val + Math.max(leftGain,rightGain);
}
}
二叉树章节算法思想总结
本章 15 题（第 25 ~ 39 题）可以概括成一句话：二叉树的题，九成是「先选一种遍历顺序，再决定这一步该干什么」。
一、三种基本遍历骨架
1. 递归 DFS（前 / 中 / 后序只差一行的位置）
void traverse(TreeNode root) {
if (root == null) {
return; // 终止条件
}
// 1. 前序位置：刚进入节点时执行
traverse(root.left);
// 2. 中序位置：左子树处理完之后执行
traverse(root.right);
// 3. 后序位置：子树全部处理完之后执行
}2. 迭代中序（显式栈）
Deque<TreeNode> stack = new ArrayDeque<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root); // 一路向左压栈
root = root.left;
}
root = stack.pop(); // 弹栈 = 访问当前最小的节点
root = root.right; // 转向右子树，重复上述过程
}3. 层序 BFS（队列 + 分层快照）
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size(); // 关键：先快照本层节点数
while (size-- > 0) {
TreeNode cur = queue.poll();
// 处理 cur
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}二、递归解题三要素与「前序位置 / 后序位置」
写树递归只问三件事：
函数语义：这个函数返回什么？（「子树最大深度」/「两棵子树是否互为镜像」/「最大单侧增益」）
终止条件：什么时候可以直接返回？（通常是
root == null）单层逻辑：拿到子问题的结果后，当前节点要做什么？
位置决定思路：
口诀：往下带约束用前序，往上要答案用后序。
三、题型分类与套路对照表
四、三个高频通用模板
模板 A：后序汇总 + 全局答案（26 / 29 / 39）
int ans = <合适的初值>; // 39 题必须是 Integer.MIN_VALUE
int dfs(TreeNode node) {
if (node == null) {
return 0; // 子问题答案（空节点）
}
int left = dfs(node.left);
int right = dfs(node.right);
ans = Math.max(ans, <用 left、right 拼出的完整答案>); // 结算"以当前节点为拐点"
return <只能选一侧的值>; // 向上汇报，不能分叉
}模板 B：自顶向下带状态 + 回溯撤销（32 / 37）
void dfs(TreeNode node, <状态参数>) {
if (node == null) {
return;
}
<进入节点：更新状态 / 登记前缀和>
<结算答案>
dfs(node.left, <新状态>);
dfs(node.right, <新状态>);
<离开节点：撤销状态（回溯）>
}模板 C：中序有序性的三种用法（31 / 33 / 36）
// 升序数组 → 平衡 BST：中点即根
TreeNode build(int[] nums, int l, int r) {
if (l > r) {
return null;
}
int mid = l + (r - l) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = build(nums, l, mid - 1);
root.right = build(nums, mid + 1, r);
return root;
}中序是 BST 的「排序视图」：建树用它（31）、找第 k 小用它（33）、还原结构也用它（36）。