二叉树
更新: 9/13/2025 字数: 0 字 时长: 0 分钟
二叉树的中序遍历
java
/**
* <p>此方法解决“二叉树的中序遍历”问题，采用<strong>递归 (Recursion)</strong> 的方式。</p>
* <p>这是最自然、最简洁的实现方式，直接体现了中序遍历“左 -> 根 -> 右”的定义。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code inorderTraversal(root)}：</strong>
* <ul>
* <li>创建一个空的 {@code List<Integer>} 来存储遍历结果。</li>
* <li>调用辅助函数 {@code inorder(root, resultList)} 开始递归遍历。</li>
* <li>返回 {@code resultList}。</li>
* </ul>
* </li>
* <li><strong>辅助函数 {@code inorder(node, resultList)}：</strong>
* <ul>
* <li><strong>基本情况 (Base Case)：</strong> 如果当前节点 {@code node} 为 {@code null}，则说明到达叶子节点以下，直接返回，停止进一步的递归。</li>
* <li><strong>递归左子树：</strong> 调用 {@code inorder(node.left, resultList)}。这会确保左子树中的所有节点都按照中序顺序被访问并添加到 {@code resultList} 中。</li>
* <li><strong>访问根节点：</strong> 将当前节点 {@code node.val} 添加到 {@code resultList} 中。这是中序遍历的核心步骤。</li>
* <li><strong>递归右子树：</strong> 调用 {@code inorder(node.right, resultList)}。这会确保右子树中的所有节点都按照中序顺序被访问并添加到 {@code resultList} 中。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被访问一次，并被添加到结果列表中一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度。</li>
* <li>在最坏情况（例如，倾斜树，所有节点都在一条线上），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> resultList = new ArrayList<>();
inorder(root, resultList);
return resultList;
}
/**
* 递归辅助函数实现中序遍历
*
* @param node 当前访问的节点
* @param resultList 存储遍历结果的列表
*/
private void inorder(TreeNode node, List<Integer> resultList) {
// 基本情况：如果节点为空，则返回
if (node == null) {
return;
}
// 1. 递归遍历左子树
inorder(node.left, resultList);
// 2. 访问当前根节点
resultList.add(node.val);
// 3. 递归遍历右子树
inorder(node.right, resultList);
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}java
/**
* <p>此方法解决“二叉树的中序遍历”问题，采用<strong>迭代 (Iteration)</strong> 的方式。</p>
* <p>通过手动维护一个栈，模拟了递归调用的过程，从而避免了递归深度可能导致的栈溢出问题。</p>
* <p>中序遍历的迭代实现核心是：先将所有左子节点压栈，直到没有左子节点，然后弹出栈顶元素访问，再转向处理右子树。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化：</strong>
* <ul>
* <li>创建一个 {@code List<Integer> resultList} 用于存储遍历结果。</li>
* <li>创建一个 {@code Stack<TreeNode> stack}。</li>
* <li>初始化一个 {@code curr} 指针指向根节点 {@code root} ({@code TreeNode curr = root;})。</li>
* </ul>
* </li>
* <li><strong>主循环：</strong> {@code while (curr != null || !stack.isEmpty())}
* <ul>
* <li><strong>a. 向左子树深入 (压栈)：</strong>
* <ul>
* <li>{@code while (curr != null)}：</li>
* <li>将当前节点 {@code curr} 压入栈中：{@code stack.push(curr);}。</li>
* <li>将 {@code curr} 移动到其左子节点：{@code curr = curr.left;}。</li>
* <li>这个 {@code while} 循环会一直执行，直到 {@code curr} 变为 {@code null} (即到达了当前路径的最左边)。</li>
* </ul>
* </li>
* <li><strong>b. 访问节点并转向右子树 (弹栈)：</strong>
* <ul>
* <li>当上一个 {@code while} 循环结束后，{@code curr} 为 {@code null}，这意味着已经到达了某个子树的最左端。此时，栈顶元素就是下一个需要被访问的节点。</li>
* <li>从栈中弹出一个节点：{@code curr = stack.pop();}。</li>
* <li>将该节点的值添加到结果列表：{@code resultList.add(curr.val);} (这是中序遍历访问节点的时机)。</li>
* <li>将 {@code curr} 移动到其右子节点：{@code curr = curr.right;}。</li>
* <li>然后回到外层 {@code while} 循环的开始，继续处理这个右子树（可能会再次进入向左深入的阶段）。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>当主循环结束时 (即 {@code curr} 为 {@code null} 且栈为空)，所有节点都已访问，返回 {@code resultList}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被压入栈一次，并弹出一次，并添加到结果列表中一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是栈在最坏情况下的最大深度（存储的节点数量）。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> resultList = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>(); // 或者使用 Deque<TreeNode> stack = new LinkedList<>();
TreeNode curr = root; // 当前遍历的节点
// 循环条件：当前节点不为空或者栈不为空，说明还有节点待处理
while (curr != null || !stack.isEmpty()) {
// 一直向左遍历并压栈，直到当前节点为空
while (curr != null) {
stack.push(curr); // 将当前节点压入栈中
curr = curr.left; // 移动到左子节点
}
// 此时 curr 为 null，说明已到达最左边，从栈中弹出一个节点
curr = stack.pop();
resultList.add(curr.val); // 访问节点（中序遍历的核心）
// 转向处理右子树
curr = curr.right;
}
return resultList;
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}二叉树的最大深度
java
/**
* <p>此方法解决“二叉树的最大深度”问题，采用<strong>递归 (Recursion)</strong> 的方式，
* 本质上是深度优先搜索 (DFS)。</p>
* <p>其核心思想是利用二叉树的递归定义：一个节点的深度等于其左右子树深度的最大值加 1。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>函数定义 {@code maxDepth(root)}：</strong>
* <ul>
* <li>这是一个递归函数，它接收一个 {@code TreeNode} (当前节点) 作为参数，并返回以该节点为根的子树的最大深度。</li>
* </ul>
* </li>
* <li><strong>基本情况 (Base Case / 递归终止条件)：</strong>
* <ul>
* <li>如果当前节点 {@code root} 为 {@code null}：
* <ul>
* <li>这意味着我们已经到达了叶子节点的下方，或者处理的是一个空树。一个空节点的深度为 {@code 0}。</li>
* <li>{@code if (root == null) { return 0; }}</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>递归关系 (Recursive Step)：</strong>
* <ul>
* <li>如果当前节点 {@code root} 不为 {@code null}：
* <ul>
* <li>递归计算其左子树的最大深度：{@code int leftDepth = maxDepth(root.left);}</li>
* <li>递归计算其右子树的最大深度：{@code int rightDepth = maxDepth(root.right);}</li>
* <li>当前节点的深度等于 {@code 1} (当前节点自身) 加上其左右子树最大深度中的较大者。
* {@code return 1 + Math.max(leftDepth, rightDepth);}</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被访问一次 (作为递归函数的参数)。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度。</li>
* <li>在最坏情况（例如，倾斜树，所有节点都在一条线上），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public int maxDepth(TreeNode root) {
// 基本情况：如果当前节点为空，则其深度为 0
if (root == null) {
return 0;
}
// 递归计算左子树的最大深度
int leftDepth = maxDepth(root.left);
// 递归计算右子树的最大深度
int rightDepth = maxDepth(root.right);
// 当前节点的深度是 1 (自身) 加上左右子树深度中的较大者
return 1 + Math.max(leftDepth, rightDepth);
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}java
/**
* <p>此方法解决“二叉树的最大深度”问题，采用<strong>迭代 (Iteration)</strong> 的方式，
* 本质上是广度优先搜索 (BFS) 或层序遍历。</p>
* <p>核心思想：通过逐层遍历二叉树，每遍历完一层，深度计数器加一，直到所有节点遍历完毕。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>特殊情况：</strong>
* <ul>
* <li>如果 {@code root} 为 {@code null}，意味着是空树，直接返回 {@code 0}。</li>
* </ul>
* </li>
* <li><strong>初始化：</strong>
* <ul>
* <li>创建一个队列 {@code Queue<TreeNode> queue} (推荐使用 {@code LinkedList} 或 {@code ArrayDeque}) 用于存储待访问的节点。</li>
* <li>将根节点 {@code root} 加入队列：{@code queue.offer(root);}。</li>
* <li>初始化深度计数器 {@code depth = 0;}。</li>
* </ul>
* </li>
* <li><strong>主循环 (层序遍历)：</strong> {@code while (!queue.isEmpty())}
* <ul>
* <li>每进入一层（即内层 {@code for} 循环开始前），深度 {@code depth} 加一：{@code depth++;}。</li>
* <li>获取当前队列中节点的数量 {@code int levelSize = queue.size();}。这个变量很重要，它代表当前层有多少个节点，我们需要在这一轮循环中全部处理掉它们，然后才能进入下一层。</li>
* <li><strong>遍历当前层的所有节点：</strong> {@code for (int i = 0; i < levelSize; i++)}
* <ul>
* <li>从队列中取出一个节点：{@code TreeNode node = queue.poll();}。</li>
* <li>如果该节点有左子节点，将其加入队列，准备在下一层处理：{@code if (node.left != null) { queue.offer(node.left); }}。</li>
* <li>如果该节点有右子节点，将其加入队列，准备在下一层处理：{@code if (node.right != null) { queue.offer(node.right); }}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>当主循环结束时 (队列为空)，所有节点都已访问，{@code depth} 存储的就是最大深度，返回 {@code depth}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被加入队列一次，并从队列中取出一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(W)}。
* <ul>
* <li>其中 {@code W} 是二叉树的最大宽度（即在同一层中节点最多的数量）。这是队列在最坏情况下需要存储的节点数量。</li>
* <li>在最坏情况（例如，完全平衡树的最后一层，或者满二叉树的倒数第二层），{@code W} 可以达到 {@code N/2}，所以空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，倾斜树），{@code W = 1}，空间复杂度为 {@code O(1)}。</li>
* </ul>
* </li>
* </ul>
*/
public int maxDepth(TreeNode root) {
// 基本情况：如果根节点为空，则深度为 0
if (root == null) {
return 0;
}
// 使用队列进行广度优先搜索 (BFS)
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 将根节点加入队列
int depth = 0; // 初始化深度
// 当队列不为空时，继续层序遍历
while (!queue.isEmpty()) {
depth++; // 每一层开始时，深度加 1
int levelSize = queue.size(); // 获取当前层的节点数量
// 遍历当前层的所有节点
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll(); // 取出当前层的节点
// 将当前节点的左右子节点（如果存在）加入队列，为下一层做准备
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return depth; // 返回最大深度
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}翻转二叉树
java
/**
* <p>此方法解决“翻转二叉树”问题，采用<strong>递归 (Recursion)</strong> 的方式，
* 本质上是深度优先搜索 (DFS)。</p>
* <p>核心思想：对于每个节点，递归地翻转其左子树和右子树，然后交换当前节点的左右子节点。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>函数定义 {@code invertTree(root)}：</strong>
* <ul>
* <li>这是一个递归函数，它接收一个 {@code TreeNode} (当前节点) 作为参数，并返回翻转后的子树的根节点。</li>
* </ul>
* </li>
* <li><strong>基本情况 (Base Case / 递归终止条件)：</strong>
* <ul>
* <li>如果当前节点 {@code root} 为 {@code null}：
* <ul>
* <li>这意味着我们到达了叶子节点下方，或者处理的是一个空树。空节点无需翻转，直接返回 {@code null}。</li>
* <li>{@code if (root == null) { return null; }}</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>递归关系 (Recursive Step)：</strong>
* <ul>
* <li>如果当前节点 {@code root} 不为 {@code null}：
* <ul>
* <li><strong>1. 递归翻转左子树：</strong>{@code TreeNode leftInverted = invertTree(root.left);}。这会返回 {@code root} 原来左子树的翻转版本。</li>
* <li><strong>2. 递归翻转右子树：</strong>{@code TreeNode rightInverted = invertTree(root.right);}。这会返回 {@code root} 原来右子树的翻转版本。</li>
* <li><strong>3. 交换当前节点的左右子节点：</strong>
* <ul>
* <li>将 {@code root} 的左指针指向 {@code rightInverted} ({@code root.left = rightInverted;})。</li>
* <li>将 {@code root} 的右指针指向 {@code leftInverted} ({@code root.right = leftInverted;})。</li>
* </ul>
* </li>
* <li><strong>4. 返回当前节点：</strong>{@code return root;}。返回这个已经翻转了其子树，并交换了左右子节点的根节点。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被访问一次，并对其子节点进行操作。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public TreeNode invertTree(TreeNode root) {
// 基本情况：如果当前节点为空，直接返回 null
if (root == null) {
return null;
}
// 递归翻转左子树，得到翻转后的左子树根节点
TreeNode leftInverted = invertTree(root.left);
// 递归翻转右子树，得到翻转后的右子树根节点
TreeNode rightInverted = invertTree(root.right);
// 交换当前节点的左右子节点
// 原来的 root.left 现在指向翻转后的右子树
root.left = rightInverted;
// 原来的 root.right 现在指向翻转后的左子树
root.right = leftInverted;
// 返回当前节点，作为其父节点的新子树
return root;
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}java
/**
* <p>此方法解决“翻转二叉树”问题，采用<strong>迭代 (Iteration)</strong> 的方式，
* 本质上是广度优先搜索 (BFS) 或层序遍历。</p>
* <p>核心思想：逐层遍历二叉树。在每一层，对当前节点执行左右子节点交换操作，然后将其子节点加入队列，以便在下一层进行同样的处理。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>特殊情况：</strong>
* <ul>
* <li>如果 {@code root} 为 {@code null}，意味着是空树，直接返回 {@code null}。</li>
* </ul>
* </li>
* <li><strong>初始化：</strong>
* <ul>
* <li>创建一个队列 {@code Queue<TreeNode> queue} (推荐使用 {@code LinkedList} 或 {@code ArrayDeque}) 用于存储待访问的节点。</li>
* <li>将根节点 {@code root} 加入队列：{@code queue.offer(root);}。</li>
* </ul>
* </li>
* <li><strong>主循环 (层序遍历)：</strong> {@code while (!queue.isEmpty())}
* <ul>
* <li>从队列中取出一个节点：{@code TreeNode node = queue.poll();}。</li>
* <li><strong>对当前节点进行翻转操作：</strong>
* <ul>
* <li>使用一个临时变量 {@code temp} 存储 {@code node.left}。</li>
* <li>将 {@code node.left} 指向 {@code node.right}。</li>
* <li>将 {@code node.right} 指向 {@code temp}。</li>
* </ul>
* </li>
* <li><strong>将交换后的子节点（如果非空）加入队列，准备在下一层处理：</strong>
* <ul>
* <li>{@code if (node.left != null) { queue.offer(node.left); }} (注意这里是新的 {@code node.left})</li>
* <li>{@code if (node.right != null) { queue.offer(node.right); }} (注意这里是新的 {@code node.right})</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>当主循环结束时 (队列为空)，所有节点都已处理完毕，返回原始的 {@code root} 引用 (因为根节点本身没有变化，只是其内部结构被翻转了)。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被加入队列一次，从队列中取出一次，并进行一次左右子节点交换。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(W)}。
* <ul>
* <li>其中 {@code W} 是二叉树的最大宽度（即在同一层中节点最多的数量）。这是队列在最坏情况下需要存储的节点数量。</li>
* <li>在最坏情况（例如，完全平衡树的最后一层），{@code W} 可以达到 {@code N/2}，所以空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，倾斜树），{@code W = 1}，空间复杂度为 {@code O(1)}。</li>
* </ul>
* </li>
* </ul>
*/
public TreeNode invertTree(TreeNode root) {
// 基本情况：如果根节点为空，直接返回 null
if (root == null) {
return null;
}
// 使用队列进行广度优先搜索 (BFS)
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 将根节点加入队列
// 当队列不为空时，继续层序遍历
while (!queue.isEmpty()) {
// 从队列中取出一个节点
TreeNode node = queue.poll();
// 交换当前节点的左右子节点
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
// 将交换后的左子节点（如果存在）加入队列，为下一层做准备
if (node.left != null) {
queue.offer(node.left);
}
// 将交换后的右子节点（如果存在）加入队列，为下一层做准备
if (node.right != null) {
queue.offer(node.right);
}
}
return root; // 返回根节点，此时整个树已翻转
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}对称二叉树
java
/**
* <p>此方法解决“对称二叉树”问题，采用<strong>递归 (Recursion)</strong> 的方式，
* 本质上是深度优先搜索 (DFS)。</p>
* <p>核心思想：判断一棵树是否是对称的，等价于判断其左子树和右子树是否互为镜像。</p>
* <p>为此，我们定义一个辅助函数 {@code isMirror} 来判断两棵树是否互为镜像。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code isSymmetric(root)}：</strong>
* <ul>
* <li><strong>特殊情况：</strong> 如果 {@code root} 为 {@code null}，空树被认为是轴对称的，返回 {@code true}。</li>
* <li>否则，调用辅助函数 {@code isMirror(root.left, root.right)} 来判断根节点的左子树和右子树是否互为镜像。</li>
* </ul>
* </li>
* <li><strong>辅助函数 {@code isMirror(node1, node2)}：</strong>
* <ul>
* <li>这是一个递归函数，接收两个 {@code TreeNode} 作为参数，判断它们是否互为镜像。</li>
* <li><strong>基本情况 (Base Cases / 递归终止条件)：</strong>
* <ul>
* <li><strong>情况 1: 两者都为空：</strong> {@code if (node1 == null && node2 == null)}。如果两个节点都为 {@code null}，它们当然是对称的，返回 {@code true}。</li>
* <li><strong>情况 2: 其中一个为空：</strong> {@code if (node1 == null || node2 == null)}。如果其中一个为 {@code null} 而另一个不为 {@code null}，它们不对称，返回 {@code false}。</li>
* <li><strong>情况 3: 值不相等：</strong> {@code if (node1.val != node2.val)}。如果两个节点的值不相等，它们不对称，返回 {@code false}。</li>
* </ul>
* </li>
* <li><strong>递归关系 (Recursive Step)：</strong>
* <ul>
* <li>如果上述基本情况都不满足（即 {@code node1} 和 {@code node2} 都非空且值相等），则需要进一步递归检查：
* <ul>
* <li>{@code node1} 的左子节点 ({@code node1.left}) 必须与 {@code node2} 的右子节点 ({@code node2.right}) 互为镜像。</li>
* <li>{@code node1} 的右子节点 ({@code node1.right}) 必须与 {@code node2} 的左子节点 ({@code node2.left}) 互为镜像。</li>
* </ul>
* </li>
* <li>只有当这两对子节点都满足镜像对称条件时，当前 {@code node1} 和 {@code node2} 才能算互为镜像。</li>
* <li>{@code return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);}</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被 {@code isMirror} 函数访问一次 (作为 {@code node1} 或 {@code node2})。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public boolean isSymmetric(TreeNode root) {
// 如果根节点为空，根据定义，空树是对称的
if (root == null) {
return true;
}
// 调用辅助函数检查根节点的左右子树是否互为镜像
return isMirror(root.left, root.right);
}
/**
* 辅助函数：判断两个节点（或子树）是否互为镜像
*
* @param node1 第一个节点
* @param node2 第二个节点
* @return 如果互为镜像则返回 true，否则返回 false
*/
private boolean isMirror(TreeNode node1, TreeNode node2) {
// 情况 1: 两个节点都为空，它们是对称的
if (node1 == null && node2 == null) {
return true;
}
// 情况 2: 其中一个节点为空，另一个不为空，它们不对称
if (node1 == null || node2 == null) {
return false;
}
// 情况 3: 两个节点的值不相等，它们不对称
if (node1.val != node2.val) {
return false;
}
// 递归检查：
// node1 的左子节点必须与 node2 的右子节点镜像对称
// node1 的右子节点必须与 node2 的左子节点镜像对称
return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}java
/**
* <p>此方法解决“对称二叉树”问题，采用<strong>迭代 (Iteration)</strong> 的方式，
* 本质上是广度优先搜索 (BFS)。</p>
* <p>核心思想：使用队列同时进行两个节点（一个在左子树，一个在右子树）的层序遍历，
* 在每一步都检查它们是否满足镜像条件。如果任何时候不满足，则树不对称。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>特殊情况：</strong>
* <ul>
* <li>如果 {@code root} 为 {@code null}，空树是对称的，直接返回 {@code true}。</li>
* </ul>
* </li>
* <li><strong>初始化：</strong>
* <ul>
* <li>创建一个队列 {@code Queue<TreeNode> queue} (推荐使用 {@code LinkedList} 或 {@code ArrayDeque})。</li>
* <li>将根节点的左孩子 {@code root.left} 和右孩子 {@code root.right} <strong>同时</strong>加入队列进行第一次配对。
* {@code queue.offer(root.left);}
* {@code queue.offer(root.right);}
* </li>
* </ul>
* </li>
* <li><strong>主循环：</strong> {@code while (!queue.isEmpty())}
* <ul>
* <li>每次循环从队列中取出两个节点进行比较：
* <ul>
* <li>{@code TreeNode node1 = queue.poll();}</li>
* <li>{@code TreeNode node2 = queue.poll();}</li>
* </ul>
* </li>
* <li><strong>比较和判断：</strong>
* <ul>
* <li><strong>情况 1: 两者都为空：</strong> {@code if (node1 == null && node2 == null)}。这对是合法的镜像，继续下一轮循环 ({@code continue;})。</li>
* <li><strong>情况 2: 其中一个为空，或者值不相等：</strong> {@code if (node1 == null || node2 == null || node1.val != node2.val)}。
* <ul>
* <li>这表示不满足镜像条件（要么结构不对称，要么值不相等），立即返回 {@code false}。</li>
* </ul>
* </li>
* <li><strong>情况 3: 两者都非空且值相等（满足当前层判断）：</strong>
* <ul>
* <li>将它们“内外侧”的子节点按照镜像配对关系重新加入队列，以便在下一轮循环中进行检查：
* <ul>
* <li>将 {@code node1.left} (左子树的外侧) 和 {@code node2.right} (右子树的外侧) 加入队列：
* {@code queue.offer(node1.left);}
* {@code queue.offer(node2.right);}
* </li>
* <li>将 {@code node1.right} (左子树的内侧) 和 {@code node2.left} (右子树的内侧) 加入队列：
* {@code queue.offer(node1.right);}
* {@code queue.offer(node2.left);}
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>如果 {@code while} 循环正常结束 (即队列为空且所有节点都通过了镜像检查)，则说明树是对称的，返回 {@code true}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点会被加入队列一次，并从队列中取出一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(W)}。
* <ul>
* <li>其中 {@code W} 是二叉树的最大宽度。队列在最坏情况下需要存储的节点数量。</li>
* <li>在最坏情况（例如，完全平衡树的最后一层），{@code W} 可以达到 {@code N/2}，所以空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，倾斜树），{@code W = 1}，空间复杂度为 {@code O(1)}。</li>
* </ul>
* </li>
* </ul>
*/
public boolean isSymmetric(TreeNode root) {
// 如果根节点为空，根据定义，空树是对称的
if (root == null) {
return true;
}
// 使用队列进行层次遍历 (BFS)
Queue<TreeNode> queue = new LinkedList<>();
// 将根节点的左子节点和右子节点一并加入队列进行配对
queue.offer(root.left);
queue.offer(root.right);
// 当队列不为空时，继续检查
while (!queue.isEmpty()) {
// 每次从队列中取出两个节点进行比较
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
// 情况 1: 两个节点都为空，它们是对称的，继续下一轮循环
if (node1 == null && node2 == null) {
continue;
}
// 情况 2: 其中一个节点为空，或者两个节点的值不相等，它们不对称，直接返回 false
// 注意：因为上面已经排除了两者都为 null 的情况，所以这里只要有一个 null 就意味着不对称
if (node1 == null || node2 == null || node1.val != node2.val) {
return false;
}
// 如果两个节点都非空且值相等，则将它们的子节点按照镜像关系加入队列
// 1. node1 的左子节点 和 node2 的右子节点 应该镜像对称
queue.offer(node1.left);
queue.offer(node2.right);
// 2. node1 的右子节点 和 node2 的左子节点 应该镜像对称
queue.offer(node1.right);
queue.offer(node2.left);
}
// 如果循环结束，所有节点都通过了镜像检查，说明树是对称的
return true;
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}二叉树的直径
java
/**
* <p>此方法解决“二叉树的直径”问题，采用<strong>递归 (Recursion)</strong> 的方式，
* 本质上是深度优先搜索 (DFS) 的后序遍历变种。</p>
* <p>核心思想：二叉树的直径可以理解为：对于树中的<strong>任意一个节点</strong>，穿过该节点的最长路径的长度。
* 这个“穿过某个节点的最长路径”等于其左子树的最大深度 + 其右子树的最大深度。</p>
* <p>因此，我们需要一个后序遍历，在处理一个节点时，先计算其左右子树的深度，然后用这两者之和更新全局最大直径。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>全局变量 {@code maxDiameter}：</strong>
* <ul>
* <li>定义一个类成员变量 {@code int maxDiameter = 0;} 用于存储遍历过程中找到的最大直径。之所以是全局或成员变量，是因为递归函数本身通常返回的是深度，而不是直径，而直径是在计算深度过程中“顺便”计算并更新的。</li>
* </ul>
* </li>
* <li><strong>主函数 {@code diameterOfBinaryTree(root)}：</strong>
* <ul>
* <li>调用辅助递归函数 {@code dfs(root)}。</li>
* <li>返回 {@code maxDiameter}。</li>
* </ul>
* </li>
* <li><strong>辅助递归函数 {@code dfs(node)}：</strong>
* <ul>
* <li><strong>作用：</strong> 计算以 {@code node} 为根的子树的最大深度，并在此过程中更新 {@code maxDiameter}。</li>
* <li><strong>返回值：</strong> 以 {@code node} 为根的子树的最大深度 (注意：不是直径)。</li>
* <li><strong>基本情况 (Base Case / 递归终止条件)：</strong>
* <ul>
* <li>如果当前节点 {@code node} 为 {@code null}，意味着到达叶子节点以下，其深度为 {@code 0}。
* {@code if (node == null) { return 0; }}</li>
* </ul>
* </li>
* <li><strong>递归调用：</strong>
* <ul>
* <li>{@code int leftDepth = dfs(node.left);}：递归计算左子树的最大深度。</li>
* <li>{@code int rightDepth = dfs(node.right);}：递归计算右子树的最大深度。</li>
* </ul>
* </li>
* <li><strong>更新 {@code maxDiameter}：</strong>
* <ul>
* <li>一条通过当前节点 {@code node} 的最长路径的长度（边数）是 {@code leftDepth + rightDepth}。
* 例如，如果左子树深度为 3，右子树深度为 2，那么经过当前节点的最长路径为 3+2=5 条边。</li>
* <li>{@code maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);}</li>
* </ul>
* </li>
* <li><strong>返回当前子树的深度：</strong>
* <ul>
* <li>以 {@code node} 为根的子树的最大深度是 {@code 1} (当前节点自身) 加上其左右子树深度的较大者。
* {@code return 1 + Math.max(leftDepth, rightDepth);}</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被访问一次，进行深度计算和直径更新。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
// 使用一个类成员变量来存储最大的直径，因为递归函数本身返回的是子树的深度
private int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
// 调用辅助函数启动深度计算和直径更新
// dfs 函数的返回值是当前子树的深度，这个返回值本身对主函数来说不重要，
// 重要的是在遍历过程中更新了 maxDiameter
dfs(root);
return maxDiameter;
}
/**
* 辅助递归函数，计算以当前节点为根的子树的最大深度，并在此过程中更新全局最大直径。
*
* @param node 当前要处理的节点
* @return 以当前节点为根的子树的最大深度（不是直径）
*/
private int dfs(TreeNode node) {
// 基本情况：如果节点为空，则其深度为 0
if (node == null) {
return 0;
}
// 递归计算左子树的最大深度
int leftDepth = dfs(node.left);
// 递归计算右子树的最大深度
int rightDepth = dfs(node.right);
// 在当前节点处，一条“穿过”该节点的最长路径长度
// 等于其左子树深度 + 右子树深度（边数）
// 这个路径长度可能就是当前或全局的最大直径
maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
// 返回以当前节点为根的子树的最大深度
// 1 代表当前节点，然后加上左右子树中较大的深度
return 1 + Math.max(leftDepth, rightDepth);
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}二叉树的层序遍历
java
/**
* <p>此方法解决“二叉树的层序遍历”问题，采用<strong>迭代 (Iteration)</strong> 的方式，
* 本质上是广度优先搜索 (BFS)。</p>
* <p>核心思想：使用队列来实现逐层遍历。在遍历每一层时，先记录当前层的节点数量，
* 然后循环处理这些节点，并将它们的子节点（如果有）加入队列，为下一层做准备。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>特殊情况：</strong>
* <ul>
* <li>如果 {@code root} 为 {@code null}，意味着是空树，返回一个空的列表 {@code []}。</li>
* </ul>
* </li>
* <li><strong>初始化：</strong>
* <ul>
* <li>创建一个 {@code List<List<Integer>> result} 用于存储最终的层序遍历结果。这是一个列表的列表，每个内部列表代表一层。</li>
* <li>创建一个队列 {@code Queue<TreeNode> queue} (推荐使用 {@code LinkedList} 或 {@code ArrayDeque}) 用于存储待访问的节点。</li>
* <li>将根节点 {@code root} 加入队列：{@code queue.offer(root);}。</li>
* </ul>
* </li>
* <li><strong>主循环 (层序遍历)：</strong> {@code while (!queue.isEmpty())}
* <ul>
* <li><strong>1. 创建当前层结果列表：</strong>{@code List<Integer> currentLevelNodes = new ArrayList<>();}。</li>
* <li><strong>2. 获取当前层的节点数量：</strong>{@code int levelSize = queue.size();}。这一步是实现“逐层”遍历的关键。在每次外层 {@code while} 循环开始时，队列中存储的就是当前层的所有节点。我们记录下它们的数量，确保只处理当前层的节点。</li>
* <li><strong>3. 遍历当前层的所有节点：</strong> {@code for (int i = 0; i < levelSize; i++)}
* <ul>
* <li>从队列中取出一个节点：{@code TreeNode node = queue.poll();}。</li>
* <li>将该节点的值添加到当前层的列表中：{@code currentLevelNodes.add(node.val);}。</li>
* <li>如果该节点有左子节点，将其加入队列，准备在下一层处理：{@code if (node.left != null) { queue.offer(node.left); }}。</li>
* <li>如果该节点有右子节点，将其加入队列，准备在下一层处理：{@code if (node.right != null) { queue.offer(node.right); }}。</li>
* </ul>
* </li>
* <li><strong>4. 将当前层结果加入最终结果：</strong>当内层 {@code for} 循环结束后，{@code currentLevelNodes} 包含了当前层的所有节点值。将其添加到 {@code result} 中：{@code result.add(currentLevelNodes);}。</li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>当主循环结束时 (队列为空)，所有节点都已访问，返回 {@code result}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被加入队列一次，并从队列中取出一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(W)}。
* <ul>
* <li>其中 {@code W} 是二叉树的最大宽度。这是队列在最坏情况下需要存储的节点数量。</li>
* <li>在最坏情况（例如，完全平衡树的最后一层），{@code W} 可以达到 {@code N/2}，所以空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，倾斜树），{@code W = 1}，空间复杂度为 {@code O(1)}。</li>
* <li>{@code result} 列表也会占用 {@code O(N)} 的空间来存储所有节点的值。</li>
* </ul>
* </li>
* </ul>
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
// 如果根节点为空，直接返回空列表
if (root == null) {
return result;
}
// 使用队列进行广度优先搜索 (BFS)
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 将根节点加入队列
// 当队列不为空时，继续层序遍历
while (!queue.isEmpty()) {
int levelSize = queue.size(); // 获取当前层的节点数量
List<Integer> currentLevelNodes = new ArrayList<>(); // 存储当前层的所有节点值
// 遍历当前层的所有节点
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll(); // 取出当前层的节点
currentLevelNodes.add(node.val); // 将节点值添加到当前层列表
// 将当前节点的左右子节点（如果存在）加入队列，为下一层做准备
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
// 将当前层的节点列表添加到最终结果中
result.add(currentLevelNodes);
}
return result; // 返回层序遍历结果
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}将有序数组转换为二叉搜索树
java
/**
* <p>此方法解决“将有序数组转换为二叉搜索树”问题，采用<strong>递归 (Recursion)</strong> 的方式，
* 本质上是分治法。</p>
* <p>核心思想：为了构建一棵平衡二叉搜索树，选择当前子数组的中间元素作为根节点。
* 然后，递归地将左半部分数组转换为左子树，将右半部分数组转换为右子树。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code sortedArrayToBST(nums)}：</strong>
* <ul>
* <li>调用辅助递归函数 {@code buildBST(nums, 0, nums.length - 1)} 来处理整个数组。</li>
* </ul>
* </li>
* <li><strong>辅助递归函数 {@code buildBST(nums, left, right)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code nums}: 升序排列的整数数组。</li>
* <li>{@code left}: 当前要构建子树的数组部分的起始索引。</li>
* <li>{@code right}: 当前要构建子树的数组部分的结束索引。</li>
* </ul>
* </li>
* <li><strong>基本情况 (Base Case / 递归终止条件)：</strong>
* <ul>
* <li>如果 {@code left > right}：这意味着当前子数组为空 (例如 {@code [mid - 1]} 结束后 {@code left} 可能会大于 {@code right})，无法创建节点，返回 {@code null}。</li>
* </ul>
* </li>
* <li><strong>构建当前节点 (Recursive Step)：</strong>
* <ul>
* <li><strong>1. 找到中间元素的索引 {@code mid}：</strong>
* {@code int mid = left + (right - left) / 2;}
* <ul>
* <li>使用这种写法可以避免 {@code left + right} 在 {@code left} 和 {@code right} 都很大时可能发生的整数溢出。</li>
* <li>{@code mid} 会是向下取整，例如 {@code (0 + 4) / 2 = 2}，{@code (0 + 3) / 2 = 1}。</li>
* </ul>
* </li>
* <li><strong>2. 创建当前根节点：</strong>
* {@code TreeNode root = new TreeNode(nums[mid]);}</li>
* <li><strong>3. 递归构建左子树：</strong>
* {@code root.left = buildBST(nums, left, mid - 1);}
* <ul>
* <li>左子树由 {@code mid} 之前的元素 (从 {@code left} 到 {@code mid-1}) 递归构成。</li>
* </ul>
* </li>
* <li><strong>4. 递归构建右子树：</strong>
* {@code root.right = buildBST(nums, mid + 1, right);}
* <ul>
* <li>右子树由 {@code mid} 之后的元素 (从 {@code mid+1} 到 {@code right}) 递归构成。</li>
* </ul>
* </li>
* <li><strong>5. 返回当前根节点：</strong>
* {@code return root;}</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是数组 {@code nums} 的长度。每个数组元素都会被创建为一个树节点。</li>
* <li>递归调用的深度为 {@code log N} (平衡树的高度)。在每层，对数组的划分和节点创建操作总共是 {@code N} 的。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(log N)}。
* <ul>
* <li>这是递归调用栈的最大深度，也就是平衡二叉搜索树的高度。</li>
* <li>在最坏情况（如果不是平衡的，但这里保证是平衡的），{@code O(N)}。</li>
* </ul>
* </li>
* </ul>
*/
public TreeNode sortedArrayToBST(int[] nums) {
// 调用辅助递归函数，起始索引为 0，结束索引为数组的最后一个元素
return buildBST(nums, 0, nums.length - 1);
}
/**
* 辅助递归函数，将给定范围内的有序数组转换为一个平衡二叉搜索树。
*
* @param nums 升序排列的整数数组
* @param left 当前子数组的起始索引
* @param right 当前子数组的结束索引
* @return 构建好的平衡二叉搜索树的根节点
*/
private TreeNode buildBST(int[] nums, int left, int right) {
// 基本情况：如果起始索引大于结束索引，表示子数组为空，返回 null
if (left > right) {
return null;
}
// 1. 找到中间元素的索引作为当前子树的根节点
// 使用 (right - left) / 2 + left 可以有效避免 left + right 可能的溢出
int mid = left + (right - left) / 2;
// 2. 创建当前根节点
TreeNode root = new TreeNode(nums[mid]);
// 3. 递归构建左子树：由中间元素左边的部分构建 (left 到 mid - 1)
root.left = buildBST(nums, left, mid - 1);
// 4. 递归构建右子树：由中间元素右边的部分构建 (mid + 1 到 right)
root.right = buildBST(nums, mid + 1, right);
// 5. 返回当前构建好的根节点
return root;
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}验证二叉搜索树
java
/**
* <p>此方法解决“验证二叉搜索树”问题，采用<strong>递归 (Recursion)</strong> 的方式，
* 并利用了二叉搜索树的定义中关于<strong>值范围（边界）</strong>的特性。</p>
* <p>核心思想：对于二叉搜索树中的任意一个节点，其值必须严格大于其左子树中所有节点的值，
* 且严格小于其右子树中所有节点的值。这意味着在递归遍历时，我们需要维护一个当前节点
* 所允许的最大值和最小值范围。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code isValidBST(root)}：</strong>
* <ul>
* <li>调用辅助递归函数 {@code isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE)}。
* <ul>
* <li>初始时，根节点没有上下限，所以我们可以将其最小值设置为 {@code Long.MIN_VALUE} (或 {@code Integer.MIN_VALUE - 1}，只要保证小于所有可能的节点值)，最大值设置为 {@code Long.MAX_VALUE} (或 {@code Integer.MAX_VALUE + 1})。使用 {@code long} 是为了处理节点值可能为 {@code Integer.MIN_VALUE} 或 {@code Integer.MAX_VALUE} 的情况，避免判断错误。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>辅助递归函数 {@code isValidBST(node, minVal, maxVal)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code node}: 当前要验证的节点。</li>
* <li>{@code minVal}: 当前节点及其子树中所有节点必须严格大于的最小值。</li>
* <li>{@code maxVal}: 当前节点及其子树中所有节点必须严格小于的最大值。</li>
* </ul>
* </li>
* <li><strong>基本情况 (Base Case / 递归终止条件)：</strong>
* <ul>
* <li>{@code if (node == null)}：如果当前节点为空，空树被认为是有效的 BST，返回 {@code true}。</li>
* </ul>
* </li>
* <li><strong>当前节点值检查：</strong>
* <ul>
* <li>{@code if (node.val <= minVal || node.val >= maxVal)}：
* <ul>
* <li>如果当前节点的值不满足 {@code minVal < node.val < maxVal} 这个条件，则它不是一个有效的 BST 节点，返回 {@code false}。</li>
* <li>注意是<strong>严格</strong>小于和<strong>严格</strong>大于。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>递归检查子树：</strong>
* <ul>
* <li>{@code return isValidBST(node.left, minVal, node.val) && isValidBST(node.right, node.val, maxVal);}</li>
* <li><strong>验证左子树：</strong>
* <ul>
* <li>{@code isValidBST(node.left, minVal, node.val)}：当递归到左子树时，左子树中的所有节点都必须小于当前节点的 {@code node.val}。所以，新的 {@code maxVal} 变成了 {@code node.val}，而 {@code minVal} 保持不变。</li>
* </ul>
* </li>
* <li><strong>验证右子树：</strong>
* <ul>
* <li>{@code isValidBST(node.right, node.val, maxVal)}：当递归到右子树时，右子树中的所有节点都必须大于当前节点的 {@code node.val}。所以，新的 {@code minVal} 变成了 {@code node.val}，而 {@code maxVal} 保持不变。</li>
* </ul>
* </li>
* <li>只有当左右子树都被成功验证为 BST 时，当前节点才有效。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被访问一次，进行值和边界的检查。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public boolean isValidBST(TreeNode root) {
// 初始调用，根节点的最大值和最小值边界设置为 Long 的极值
// 使用 long 是为了处理节点值可能为 Integer.MIN_VALUE 或 Integer.MAX_VALUE 的情况
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
/**
* 辅助递归函数，验证以 node 为根的子树是否是有效的 BST。
*
* @param node 当前要验证的节点
* @param minVal 当前节点及其所有子孙节点必须严格大于的最小值
* @param maxVal 当前节点及其所有子孙节点必须严格小于的最大值
* @return 如果以 node 为根的子树是有效的 BST，则返回 true，否则返回 false
*/
private boolean isValidBST(TreeNode node, long minVal, long maxVal) {
// 基本情况：如果节点为空，则它是有效的 BST (空树是有效的)
if (node == null) {
return true;
}
// 检查当前节点的值是否在合法范围内
// node.val 必须严格大于 minVal 且 严格小于 maxVal
if (node.val <= minVal || node.val >= maxVal) {
return false;
}
// 递归检查左子树和右子树
// 1. 验证左子树：左子树的所有节点必须小于当前节点的值（node.val 成为新的 maxVal）
// 且大于原来的 minVal 不变
boolean leftIsValid = isValidBST(node.left, minVal, node.val);
// 2. 验证右子树：右子树的所有节点必须大于当前节点的值（node.val 成为新的 minVal）
// 且小于原来的 maxVal 不变
boolean rightIsValid = isValidBST(node.right, node.val, maxVal);
// 只有当左右子树都有效时，当前节点组成的子树才有效
return leftIsValid && rightIsValid;
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}java
/**
* <p>此方法解决“验证二叉搜索树”问题，采用<strong>中序遍历 (In-order Traversal)</strong> 的方式。</p>
* <p>核心思想：对一个有效的二叉搜索树进行中序遍历，将得到一个严格升序排列的节点值序列。
* 因此，我们只需要在中序遍历的过程中，检查当前节点的值是否严格大于前一个访问过的节点的值即可。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>全局变量 {@code prev}：</strong>
* <ul>
* <li>定义一个类成员变量 {@code long prev = Long.MIN_VALUE;}。这个变量用于存储中序遍历中上一个访问到的节点的值。初始值设置为 {@code Long.MIN_VALUE}，以确保第一个节点的任何有效值都可以通过检查。使用 {@code long} 是为了处理节点值可能为 {@code Integer.MIN_VALUE} 的情况。</li>
* </ul>
* </li>
* <li><strong>主函数 {@code isValidBST(root)}：</strong>
* <ul>
* <li>调用辅助递归函数 {@code inorderTraversal(root)}。</li>
* </ul>
* </li>
* <li><strong>辅助递归函数 {@code inorderTraversal(node)}：</strong> (类似于标准的 In-order Traversal)
* <ul>
* <li><strong>参数：</strong> {@code node}: 当前要处理的节点。</li>
* <li><strong>返回值：</strong> {@code boolean}，表示以当前节点为根的子树（及其后续处理）是否构成有效 BST。</li>
* <li><strong>基本情况 (Base Case / 递归终止条件)：</strong>
* <ul>
* <li>{@code if (node == null)}：如果当前节点为空，它没有违反 BST 规则，返回 {@code true}。</li>
* </ul>
* </li>
* <li><strong>递归处理左子树：</strong>
* <ul>
* <li>{@code if (!inorderTraversal(node.left)) { return false; }}</li>
* <li>如果左子树的验证失败，则整个树都无效，立即返回 {@code false}。</li>
* </ul>
* </li>
* <li><strong>处理当前节点：</strong> (在中序遍历中，这是访问节点的时机)
* <ul>
* <li>{@code if (node.val <= prev)}：
* <ul>
* <li>如果当前节点的值不严格大于前一个 ({@code prev}) 节点的值，则违反了 BST 的特性（中序遍历结果非严格升序）。
* 立即返回 {@code false}。</li>
* </ul>
* </li>
* <li>{@code prev = node.val;}：
* <ul>
* <li>更新 {@code prev} 为当前节点的值，供下一个节点比较。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>递归处理右子树：</strong>
* <ul>
* <li>{@code return inorderTraversal(node.right);}</li>
* <li>返回右子树的验证结果。如果右子树验证失败，也会层层返回 {@code false}。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>优点：</h3>
* <ul>
* <li>概念直观，符合 BST 中序遍历的数学性质。</li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被访问一次。在最坏情况下（树不是 BST），可能提前中断遍历。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
// 用一个全局变量（或成员变量）来存储中序遍历的前一个节点的值
// 初始值设为 Long.MIN_VALUE 以确保第一个节点的值能被正确比较
private long prev = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
return inorderTraversal(root);
}
/**
* 辅助递归函数，执行中序遍历并验证 BST 属性。
*
* @param node 当前要访问的节点
* @return 如果以当前节点为根的子树（以及之前遍历的部分）是有效的 BST，则返回 true，否则返回 false。
*/
private boolean inorderTraversal(TreeNode node) {
// 基本情况：如果节点为空，则它是有效的 (空的部分不会破坏 BST 属性)
if (node == null) {
return true;
}
// 1. 递归遍历左子树
if (!inorderTraversal(node.left)) {
return false; // 如果左子树无效，则整个树无效
}
// 2. 访问当前节点
// 检查当前节点的值是否严格大于前一个访问的节点的值
if (node.val <= prev) {
return false; // 如果不满足严格升序，则不是有效的 BST
}
// 更新 prev 为当前节点的值
prev = node.val;
// 3. 递归遍历右子树
return inorderTraversal(node.right);
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}java
/**
* <p>此方法解决“验证二叉搜索树”问题，采用<strong>迭代 (Iteration)</strong> 的方式，
* 利用<strong>中序遍历 (In-order Traversal)</strong> 的特性，使用<strong>栈 (Stack)</strong>实现。</p>
* <p>核心思想：二叉搜索树的中序遍历结果是一个严格升序的序列。我们可以迭代地模拟中序遍历，
* 并在此过程中检查当前节点的值是否严格大于前一个节点的值。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化：</strong>
* <ul>
* <li>创建一个 {@code Stack<TreeNode> stack} 用于存储待访问的节点。</li>
* <li>初始化 {@code TreeNode curr = root;}，表示当前正在处理的节点。</li>
* <li>初始化 {@code long prev = Long.MIN_VALUE;}，用于记录中序遍历中前一个访问过的节点的值。使用 {@code long} 是为了处理节点值可能为 {@code Integer.MIN_VALUE} 的情况，避免边缘错误。</li>
* </ul>
* </li>
* <li><strong>主循环：</strong> {@code while (curr != null || !stack.isEmpty())}
* <ul>
* <li><strong>1. 探索左子树：</strong>
* <ul>
* <li>{@code while (curr != null)}：
* <ul>
* <li>将 {@code curr} 节点压入栈：{@code stack.push(curr);}。</li>
* <li>移动到其左子节点：{@code curr = curr.left;}。</li>
* <li>这一步会一直深入到最左侧的节点。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>2. 访问当前节点 (出栈)：</strong>
* <ul>
* <li>{@code curr = stack.pop();}：从栈中弹出一个节点。这是中序遍历中“访问根节点”的时机。</li>
* <li><strong>验证：</strong> {@code if (curr.val <= prev)}：
* <ul>
* <li>如果当前节点的值不严格大于 {@code prev}，则违反了 BST 的规则，返回 {@code false}。</li>
* </ul>
* </li>
* <li><strong>更新 {@code prev}：</strong> {@code prev = curr.val;}。</li>
* </ul>
* </li>
* <li><strong>3. 探索右子树：</strong>
* <ul>
* <li>{@code curr = curr.right;}：将 {@code curr} 移动到当前节点的右子节点。在下一轮循环中，会再次将这个右子节点及其所有左子节点压入栈。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>如果循环正常结束，说明所有节点都通过了验证，返回 {@code true}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被压入栈一次，并从栈中弹出一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是栈在最坏情况下需要存储的节点数量。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
// 使用 Long.MIN_VALUE 作为前一个节点值的初始值，确保第一个有效节点能通过检查
long prev = Long.MIN_VALUE;
while (curr != null || !stack.isEmpty()) {
// 1. 不断将当前节点及其左子节点压入栈，直到左子节点为空
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
// 2. 从栈中弹出一个节点，这是中序遍历中访问该节点的时机
curr = stack.pop();
// 3. 检查当前节点的值是否严格大于前一个节点的值
if (curr.val <= prev) {
return false; // 如果不满足 BST 的中序遍历特性，则不是有效的 BST
}
// 更新 prev 为当前节点的值
prev = curr.val;
// 4. 转向处理右子树
curr = curr.right;
}
// 如果循环结束，所有节点都通过了检查，说明是有效的 BST
return true;
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}二叉搜索树中第 K 小的元素
java
/**
* <p>此方法解决“二叉搜索树中第 K 小的元素”问题，采用<strong>迭代 (Iteration)</strong> 的方式，
* 利用<strong>中序遍历 (In-order Traversal)</strong> 特性，并使用<strong>栈 (Stack)</strong>实现。</p>
* <p>核心思想：与递归方法相同，利用 BST 中序遍历结果是严格升序的特性。迭代实现避免了递归栈的深度限制，
* 但原理是相同的，只是手动管理了遍历的流程。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化：</strong>
* <ul>
* <li>创建一个 {@code Stack<TreeNode> stack} 用于模拟递归栈。</li>
* <li>初始化 {@code TreeNode curr = root;}，表示当前正在处理的节点。</li>
* <li>初始化 {@code int count = 0;}，用于记录已经访问的节点数量。</li>
* </ul>
* </li>
* <li><strong>主循环：</strong> {@code while (curr != null || !stack.isEmpty())}
* <ul>
* <li><strong>1. 探索左子树 (入栈过程)：</strong>
* <ul>
* <li>{@code while (curr != null)}：
* <ul>
* <li>将当前节点 {@code curr} 压入栈：{@code stack.push(curr);}。</li>
* <li>将 {@code curr} 移动到其左子节点：{@code curr = curr.left;}。</li>
* <li>这一步骤会一直向下，直到找到最左侧的子节点（该节点没有左子节点，或者它自身就是 null）。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>2. 访问当前节点 (出栈过程)：</strong>
* <ul>
* <li>{@code curr = stack.pop();}：从栈顶弹出一个节点。这是中序遍历中“访问根节点”的时机（实际上是指当前子树的最左节点或某个父节点）。</li>
* <li>{@code count++;}：递增计数器。</li>
* <li>{@code if (count == k)}：
* <ul>
* <li>如果 {@code count} 达到 {@code k}，说明当前节点就是我们要找的第 K 小的元素。</li>
* <li>{@code return curr.val;}：直接返回该节点的值。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>3. 探索右子树：</strong>
* <ul>
* <li>{@code curr = curr.right;}：将 {@code curr} 移动到当前节点的右子节点。下一轮循环将从这个右子节点开始，继续探索其左子树。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>返回结果：</strong> (如果程序执行到这里，说明 k 值超出了树的节点总数，虽然根据题意不会发生，但作为健壮性考虑)
* <ul>
* <li>返回一个不合法的值，或者抛出异常。根据题目，{@code k} 总是有效的。</li>
* </ul>
* </li>
* </ol>
*
* <h3>优点：</h3>
* <ul>
* <li>避免了递归栈的深度限制，对于非常深的树可能更安全。</li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(H + k)}。
* <ul>
* <li>其中 {@code H} 是二叉搜索树的高度。与递归版本类似，遍历的节点数不会超过 {@code k} 个。</li>
* <li>实际上是 {@code O(min(N, k))}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>这是栈在最坏情况下需要存储的节点数量，即树的高度。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
int count = 0; // 记录已遍历的节点数
// 循环直到当前节点为空且栈也为空
while (curr != null || !stack.isEmpty()) {
// 1. 将当前节点及其所有左子节点压入栈
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
// 2. 从栈中弹出一个节点，进行访问
curr = stack.pop();
count++; // 访问计数器递增
// 3. 如果当前计数达到 k，说明找到了第 k 小的元素
if (count == k) {
return curr.val;
}
// 4. 继续处理右子树
curr = curr.right;
}
// 如果 k 大于树的节点总数，理论上不会走到这里，根据题目约束 k 总是有效的
// 如果题目允许 k 无效，这里可能需要抛出异常或返回特定值
return -1; // 作为示例，返回一个错误值，实际情况依赖题目或约定
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}二叉树的右视图
java
/**
* <p>此方法解决“二叉树的右视图”问题，采用<strong>深度优先搜索 (DFS)</strong> 的方式。</p>
* <p>核心思想：从右侧看二叉树时，每一层可见的节点只有一个，即该层最右边的节点。
* 在 DFS 遍历时，我们可以通过<strong>优先遍历右子树</strong>的方式，确保在第一次访问到某个层级时，
* 该节点就是该层最右边的节点。我们可以使用一个变量来跟踪当前已经发现的最大层级。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code rightSideView(root)}：</strong>
* <ul>
* <li>创建一个 {@code List<Integer> result} 用于存储右视图的节点值。</li>
* <li>调用辅助递归函数 {@code dfs(root, 0, result)}。
* <ul>
* <li>{@code root} 是根节点。</li>
* <li>{@code 0} 是初始层级（根节点在第 0 层）。</li>
* <li>{@code result} 列表用于收集结果。</li>
* </ul>
* </li>
* <li>返回 {@code result}。</li>
* </ul>
* </li>
* <li><strong>辅助递归函数 {@code dfs(node, level, result)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code node}: 当前正在访问的节点。</li>
* <li>{@code level}: 当前节点所在的层级（根节点为 0, 其子节点为 1, 以此类推）。</li>
* <li>{@code result}: 收集右视图节点值的列表。</li>
* </ul>
* </li>
* <li><strong>基本情况 (Base Case / 递归终止条件)：</strong>
* <ul>
* <li>{@code if (node == null)}：如果当前节点为空，则返回。</li>
* </ul>
* </li>
* <li><strong>核心逻辑：</strong>
* <ul>
* <li>{@code if (level == result.size())}：
* <ul>
* <li>这个条件判断非常关键。它表示我们<strong>第一次</strong>到达 {@code level} 这一层。</li>
* <li>由于我们是<strong>优先递归右子树</strong>的，所以当前 {@code node} 必然是这一层中第一个被访问到的节点。在右视图中，同一层最右边的节点就是我们想要的。因此，我们将其值加入 {@code result}。</li>
* <li>例如，{@code result.size()} 是 0，{@code level} 是 0，{@code root} 被加入。{@code result.size()} 变成 1。
* 当到达第 1 层时，{@code level} 是 1。{@code result.size()} 此时是 1。1 == 1，所以第 1 层的第一个节点（最右边的）被加入。</li>
* </ul>
* </li>
* <li>{@code result.add(node.val);}：将当前节点的值添加到 {@code result} 中。</li>
* </ul>
* </li>
* <li><strong>递归调用 (优先右子树)：</strong>
* <ul>
* <li>{@code dfs(node.right, level + 1, result);}：首先递归右子树。这是关键，确保在同一层中，右边的节点会比左边的节点先被访问到 (因为遍历顺序是 根 -> 右 -> 左)。</li>
* <li>{@code dfs(node.left, level + 1, result);}：然后再递归左子树。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被访问一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
// 从根节点开始 DFS 遍历，初始层级为 0
dfs(root, 0, result);
return result;
}
/**
* 辅助递归函数，用于进行深度优先搜索并收集右视图的节点。
*
* @param node 当前访问的节点
* @param level 当前节点所在的层级（根节点为 0）
* @param result 存储右视图节点值的列表
*/
private void dfs(TreeNode node, int level, List<Integer> result) {
// 基本情况：如果节点为空，则返回
if (node == null) {
return;
}
// 核心逻辑：
// 如果当前层级的列表还未被填充 (即 result.size() == level)，
// 说明这是第一次访问到这一层。由于我们优先遍历右子树，
// 则当前节点必然是该层最右边的节点（或第一个被看到的节点）。
if (level == result.size()) {
result.add(node.val);
}
// 优先递归右子树
dfs(node.right, level + 1, result);
// 后递归左子树
dfs(node.left, level + 1, result);
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}java
/**
* <p>此方法解决“二叉树的右视图”问题，采用<strong>广度优先搜索 (BFS)</strong> 的方式，
* 本质上是层序遍历，并对每一层的最后一个节点进行记录。</p>
* <p>核心思想：对于二叉树的每一层，从右侧观察时，只能看到该层最右边的节点。
* 在层序遍历中，我们逐层处理节点。如果处理顺序是从左到右，那么每一层的最后一个被处理的节点就是最右边的节点。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>特殊情况：</strong>
* <ul>
* <li>如果 {@code root} 为 {@code null}，意味着是空树，返回一个空的列表 {@code []}。</li>
* </ul>
* </li>
* <li><strong>初始化：</strong>
* <ul>
* <li>创建一个 {@code List<Integer> result} 用于存储右视图的节点值。</li>
* <li>创建一个队列 {@code Queue<TreeNode> queue} (推荐使用 {@code LinkedList} 或 {@code ArrayDeque}) 用于进行 BFS。</li>
* <li>将根节点 {@code root} 加入队列：{@code queue.offer(root);}。</li>
* </ul>
* </li>
* <li><strong>主循环 (层序遍历)：</strong> {@code while (!queue.isEmpty())}
* <ul>
* <li><strong>1. 获取当前层的节点数量：</strong>{@code int levelSize = queue.size();}。
* <ul>
* <li>这一步是实现“逐层”处理的关键。在每次外层 {@code while} 循环开始时，队列中存储的就是当前层的所有节点。</li>
* </ul>
* </li>
* <li><strong>2. 声明一个变量 {@code lastNodeVal} 来存储当前层最右边的节点值。</strong></li>
* <li><strong>3. 遍历当前层的所有节点：</strong> {@code for (int i = 0; i < levelSize; i++)}
* <ul>
* <li>从队列中取出一个节点：{@code TreeNode node = queue.poll();}。</li>
* <li>{@code lastNodeVal = node.val;}：每次取出节点后，都更新 {@code lastNodeVal}。当 {@code for} 循环结束时，{@code lastNodeVal} 将保存该层最后一个（即最右边）访问的节点的值。</li>
* <li>如果该节点有左子节点，将其加入队列，准备在下一层处理：{@code if (node.left != null) { queue.offer(node.left); }}。</li>
* <li>如果该节点有右子节点，将其加入队列，准备在下一层处理：{@code if (node.right != null) { queue.offer(node.right); }}。</li>
* </ul>
* <p><strong>注意：</strong> 按照 BFS 的常规做法，左右子节点都会被加入。由于我们关心的是最右侧的节点，只要保证在 {@code for} 循环中记录最后一个访问的节点即可。</p>
* </li>
* <li><strong>4. 将当前层最右节点值加入结果：</strong>当内层 {@code for} 循环结束后，{@code lastNodeVal} 中就是该层最右侧的节点值。将其添加到 {@code result} 中：{@code result.add(lastNodeVal);}。</li>
* </ul>
* </li>
* <li><strong>返回结果：</strong>
* <ul>
* <li>当主循环结束时 (队列为空)，所有节点都已访问，返回 {@code result}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被加入队列一次，并从队列中取出一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(W)}。
* <ul>
* <li>其中 {@code W} 是二叉树的最大宽度。这是队列在最坏情况下需要存储的节点数量。</li>
* <li>在最坏情况（例如，完全平衡树的最后一层），{@code W} 可以达到 {@code N/2}，所以空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，倾斜树），{@code W = 1}，空间复杂度为 {@code O(1)}。</li>
* <li>{@code result} 列表也会占用 {@code O(N)} 的空间来存储所有节点的值。</li>
* </ul>
* </li>
* </ul>
*/
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
// 如果根节点为空，直接返回空列表
if (root == null) {
return result;
}
// 使用队列进行广度优先搜索 (BFS)
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 将根节点加入队列
// 当队列不为空时，继续层序遍历
while (!queue.isEmpty()) {
int levelSize = queue.size(); // 获取当前层的节点数量
int lastNodeVal = 0; // 存储当前层最右边的节点值
// 遍历当前层的所有节点
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll(); // 取出当前层的节点
lastNodeVal = node.val; // 每次取出节点都更新，确保最后一次更新的是最右边的节点
// 将当前节点的左右子节点（如果存在）加入队列，为下一层做准备
// 注意这里先加左子节点再加右子节点，保证了在同一层中右子节点后被处理，从而正确捕捉到最右侧的元素
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
// 将当前层的最右节点值添加到最终结果中
result.add(lastNodeVal);
}
return result; // 返回右视图结果
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}二叉树展开为链表
java
/**
* <p>此方法解决“二叉树展开为链表”问题，采用<strong>原地修改的深度优先搜索 (DFS)</strong> 方式，
* 具体是遍历时，将当前节点的左子树插入到当前节点和其原右子树之间。</p>
* <p>核心思想：在展开的单链表中，节点顺序与二叉树的先序遍历顺序相同（根 -> 左 -> 右）。
* 对于当前节点 {@code root}：
* 1. 将其左子树展开后，新的右指针应该指向 {@code root} 的原右子树的头部。
* 2. {@code root} 的 {@code right} 指针应该指向其展开后的左子树的头部。
* 3. {@code root} 的 {@code left} 指针应该为 {@code null}。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code flatten(root)}：</strong>
* <ul>
* <li>如果 {@code root} 为 {@code null}，直接返回，没有需要展开的树。</li>
* <li>调用辅助递归函数 (或者直接在主函数中实现，因为我们不需要返回特定值)。</li>
* </ul>
* </li>
* <li><strong>递归展开过程 (在 {@code flatten} 函数内部实现)：</strong> {@code while (root != null)}
* <ul>
* <li><strong>1. 检查左子节点：</strong>
* <ul>
* <li>{@code if (root.left != null)}：如果当前节点 {@code root} 有左子节点。
* <ul>
* <li><strong>a. 找到左子树的最右节点：</strong>
* <ul>
* <li>创建一个临时指针 {@code TreeNode pre = root.left;}。</li>
* <li>循环 {@code while (pre.right != null)} 将 {@code pre} 移动到左子树的最后一个节点（即左子树展开后的尾部）。</li>
* </ul>
* </li>
* <li><strong>b. 将原右子树接到左子树的尾部：</strong>
* <ul>
* <li>{@code pre.right = root.right;}。这样就保证了 {@code root} 的原右子树不会丢失，并接在了其左子树的末尾。</li>
* </ul>
* </li>
* <li><strong>c. 将左子树接到 {@code root} 的右边：</strong>
* <ul>
* <li>{@code root.right = root.left;}。现在 {@code root} 的右指针指向了其左子树的头部。</li>
* </ul>
* </li>
* <li><strong>d. 清空 {@code root} 的左指针：</strong>
* <ul>
* <li>{@code root.left = null;}。符合单链表的定义。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>2. 移动到下一个节点：</strong>
* <ul>
* <li>{@code root = root.right;}。继续处理当前节点在新右指针指向的下一个节点。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都会被主循环访问一次。</li>
* <li>在 {@code while (pre.right != null)} 循环中，{@code pre} 最多会移动 {@code H} 次 (树的高度)。
* 然而，每个节点被 {@code pre} 访问的次数总和起来是 {@code N} (因为一个节点的左子树最右节点就是通过遍历其左子树的路径找到的)。</li>
* <li>可以理解为，总的指针操作次数与节点数量成正比。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>因为是原地修改，除了几个临时指针变量，没有额外的数据结构（如栈或列表）占用与树规模相关的空间。</li>
* </ul>
* </li>
* </ul>
*/
public void flatten(TreeNode root) {
// 如果根节点为空，或者已经是一个叶子节点 (没有子节点)，则无需操作
if (root == null) {
return;
}
// 迭代处理每个节点
TreeNode curr = root;
while (curr != null) {
// 如果当前节点有左子节点
if (curr.left != null) {
// 找到左子树的最右节点 (用于连接原右子树)
// pre 指针将遍历到当前节点左子树的最深右节点
TreeNode pre = curr.left;
while (pre.right != null) {
pre = pre.right;
}
// 将当前节点的右子树连接到左子树的最右节点的右指针
pre.right = curr.right;
// 将当前节点的左子树移动到当前节点的右指针
curr.right = curr.left;
// 将当前节点的左子指针置为 null (符合链表要求)
curr.left = null;
}
// 移动到下一个节点（原先的右子节点，或者现在的左子树的根节点）
curr = curr.right;
}
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}从前序与中序遍历序列构造二叉树
java
/**
* <p>此方法解决“从前序与中序遍历序列构造二叉树”问题，采用<strong>递归 (Recursion)</strong> 的方式，
* 并辅以<strong>哈希表 (HashMap)</strong> 来高效查找中序遍历中根节点的位置。</p>
* <p>核心思想：</p>
* <ol>
* <li><strong>前序遍历</strong>的第一个元素永远是当前（子）树的<strong>根节点</strong>。</li>
* <li><strong>中序遍历</strong>中，根节点将序列<strong>分成两部分</strong>：根节点左边是左子树的所有节点，根节点右边是右子树的所有节点。</li>
* </ol>
*
* <p>结合这两个特性，我们可以递归地构建二叉树：</p>
* <ul>
* <li>每次递归，都以前序遍历的第一个元素作为当前子树的根。</li>
* <li>在中序遍历中找到这个根，从而确定左右子树的节点范围和数量。</li>
* <li>根据左右子树的节点数量，在前序遍历中划分出左右子树对应的子序列。</li>
* <li>递归调用自身去构建左右子树。</li>
* </ul>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>构造中序遍历值到索引的映射：</strong>
* <ul>
* <li>创建一个 {@code Map<Integer, Integer> inorderMap}。</li>
* <li>遍历 {@code inorder} 数组，将每个节点值与其在数组中的索引存入 {@code inorderMap}。这样做可以使在中序遍历中查找根节点位置的操作从 {@code O(N)} 降到 {@code O(1)}。</li>
* </ul>
* </li>
* <li><strong>主函数 {@code buildTree(preorder, inorder)}：</strong>
* <ul>
* <li>进行上述 {@code inorderMap} 的初始化。</li>
* <li>调用辅助递归函数 {@code buildTreeRecursive(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderMap)}。</li>
* </ul>
* </li>
* <li><strong>辅助递归函数 {@code buildTreeRecursive(preorder, pStart, pEnd, inorder, iStart, iEnd, inorderMap)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code preorder}: 完整的先序遍历数组。</li>
* <li>{@code pStart}, {@code pEnd}: 当前递归调用所处理的子树在 {@code preorder} 数组中的起始和结束索引。</li>
* <li>{@code inorder}: 完整的中序遍历数组。</li>
* <li>{@code iStart}, {@code iEnd}: 当前递归调用所处理的子树在 {@code inorder} 数组中的起始和结束索引。</li>
* <li>{@code inorderMap}: 中序遍历值到索引的映射。</li>
* </ul>
* </li>
* <li><strong>基本情况 (Base Case / 递归终止条件)：</strong>
* <ul>
* <li>{@code if (pStart > pEnd || iStart > iEnd)}：
* <ul>
* <li>如果前序遍历的起始索引大于结束索引，或者中序遍历的起始索引大于结束索引，这意味着当前子树为空，返回 {@code null}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>核心逻辑：</strong>
* <ul>
* <li><strong>1. 确定当前子树的根节点：</strong>
* <ul>
* <li>{@code int rootVal = preorder[pStart];}：前序遍历的第一个元素就是当前子树的根节点的值。</li>
* <li>{@code TreeNode root = new TreeNode(rootVal);}：创建根节点。</li>
* </ul>
* </li>
* <li><strong>2. 查找根节点在中序遍历中的位置：</strong>
* <ul>
* <li>{@code int rootInorderIndex = inorderMap.get(rootVal);}：利用哈希表高效查找。</li>
* </ul>
* </li>
* <li><strong>3. 计算左子树的节点数量：</strong>
* <ul>
* <li>{@code int leftSubtreeSize = rootInorderIndex - iStart;}：在中序遍历中，{@code iStart} 到 {@code rootInorderIndex - 1} 都是左子树的节点。</li>
* </ul>
* </li>
* <li><strong>4. 递归构建左子树：</strong>
* <ul>
* <li>{@code root.left = buildTreeRecursive(preorder, pStart + 1, pStart + leftSubtreeSize, inorder, iStart, rootInorderIndex - 1, inorderMap);}</li>
* <li>{@code pStart + 1} 是左子树在前序遍历中的开始位置（跳过当前的根）。</li>
* <li>{@code pStart + leftSubtreeSize} 是左子树在前序遍历中的结束位置。</li>
* <li>{@code iStart} 到 {@code rootInorderIndex - 1} 是左子树在中序遍历中的范围。</li>
* </ul>
* </li>
* <li><strong>5. 递归构建右子树：</strong>
* <ul>
* <li>{@code root.right = buildTreeRecursive(preorder, pStart + leftSubtreeSize + 1, pEnd, inorder, rootInorderIndex + 1, iEnd, inorderMap);}</li>
* <li>{@code pStart + leftSubtreeSize + 1} 是右子树在前序遍历中的开始位置（跳过当前的根和所有左子树节点）。</li>
* <li>{@code pEnd} 是右子树在前序遍历中的结束位置。</li>
* <li>{@code rootInorderIndex + 1} 到 {@code iEnd} 是右子树在中序遍历中的范围。</li>
* </ul>
* </li>
* <li><strong>6. 返回当前根节点。</strong></li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。
* <li>构建 {@code inorderMap} 需要 {@code O(N)} 时间。</li>
* <li>递归函数中，每个节点都会被创建一次，并且对 {@code inorderMap} 的查找操作是 {@code O(1)}。
* 每个节点最多被访问一次来构建自身及其子节点。</li>
* <li>因此，总时间复杂度为 {@code O(N)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>{@code inorderMap} 会存储 {@code N} 个键值对，占用 {@code O(N)} 空间。</li>
* <li>递归调用栈的最大深度为 {@code H} (树的高度)。在最坏情况下（倾斜树），{@code H = N}，栈空间也是 {@code O(N)}。</li>
* <li>因此，总空间复杂度为 {@code O(N)}。</li>
* </ul>
* </li>
* </ul>
*/
// 哈希表用于存储中序遍历中每个值及其索引，以便 O(1) 查找
private Map<Integer, Integer> inorderMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
return null;
}
inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
// 调用递归函数构建二叉树
// pStart, pEnd: 前序遍历子数组的起始和结束索引
// iStart, iEnd: 中序遍历子数组的起始和结束索引
return buildTreeRecursive(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
}
/**
* 递归构建二叉树的辅助函数。
*
* @param preorder 完整的前序遍历数组
* @param pStart 当前子树在前序遍历数组中的起始索引
* @param pEnd 当前子树在前序遍历数组中的结束索引
* @param inorder 完整的中序遍历数组
* @param iStart 当前子树在中序遍历数组中的起始索引
* @param iEnd 当前子树在中序遍历数组中的结束索引
* @return 构建的子树的根节点
*/
private TreeNode buildTreeRecursive(int[] preorder, int pStart, int pEnd,
int[] inorder, int iStart, int iEnd) {
// 基本情况：如果当前子数组为空（起始索引大于结束索引），返回 null
if (pStart > pEnd || iStart > iEnd) {
return null;
}
// 1. 前序遍历的第一个元素是当前子树的根节点值
int rootVal = preorder[pStart];
TreeNode root = new TreeNode(rootVal);
// 2. 在中序遍历中找到根节点的位置
int rootInorderIndex = inorderMap.get(rootVal);
// 3. 计算左子树的节点数量
// 左子树的节点数量 = 根节点在中序遍历中的索引 - 中序遍历的起始索引
int leftSubtreeSize = rootInorderIndex - iStart;
// 4. 递归构建左子树
// 左子树的前序遍历范围：从 pStart + 1 开始，到 pStart + leftSubtreeSize 结束
// 左子树的中序遍历范围：从 iStart 开始，到 rootInorderIndex - 1 结束
root.left = buildTreeRecursive(preorder, pStart + 1, pStart + leftSubtreeSize,
inorder, iStart, rootInorderIndex - 1);
// 5. 递归构建右子树
// 右子树的前序遍历范围：从 pStart + leftSubtreeSize + 1 开始，到 pEnd 结束
// 右子树的中序遍历范围：从 rootInorderIndex + 1 开始，到 iEnd 结束
root.right = buildTreeRecursive(preorder, pStart + leftSubtreeSize + 1, pEnd,
inorder, rootInorderIndex + 1, iEnd);
return root;
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}路径总和 III
java
/**
* <p>此方法解决“路径总和 III”问题，采用<strong>双重深度优先搜索 (DFS)</strong> 的方式。</p>
* <p>核心思想：由于路径可以从任何节点开始，到任何节点结束（只要方向向下），
* 我们需要对树中的每一个节点都进行一次深度优先搜索，将该节点作为路径的起点，
* 然后向下查找所有和为 {@code targetSum} 的路径。</p>
* <p>这实际上是两个 DFS 函数的嵌套调用：</p>
* <ol>
* <li><strong>外层 DFS ({@code pathSum})：</strong> 遍历树中的所有节点，将每个节点都作为一次内层 DFS 的起点。</li>
* <li><strong>内层 DFS ({@code countPathsFromNode})：</strong> 从一个给定的起点向下遍历，查找所有满足 {@code targetSum} 的路径。</li>
* </ol>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code pathSum(root, targetSum)} (外层 DFS)：</strong>
* <ul>
* <li><strong>参数：</strong> {@code root} 当前节点，{@code targetSum} 目标和。</li>
* <li><strong>返回：</strong> 以 {@code root} 为根的子树中，所有符合条件的路径总数。</li>
* <li><strong>基本情况：</strong>
* <ul>
* <li>{@code if (root == null) return 0;}：如果节点为空，则没有路径，返回 0。</li>
* </ul>
* </li>
* <li><strong>核心逻辑：</strong>
* <ul>
* <li>{@code int count = countPathsFromNode(root, targetSum);}：
* 计算<strong>以当前 {@code root} 节点为起点</strong>的所有路径中，和为 {@code targetSum} 的路径数量。</li>
* <li>{@code count += pathSum(root.left, targetSum);}：
* 递归地计算<strong>左子树中</strong>所有节点作为起点（包括左子树的根节点）的路径数量。</li>
* <li>{@code count += pathSum(root.right, targetSum);}：
* 递归地计算<strong>右子树中</strong>所有节点作为起点（包括右子树的根节点）的路径数量。</li>
* <li>{@code return count;}：返回总数。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>辅助函数 {@code countPathsFromNode(node, currentTargetSum)} (内层 DFS)：</strong>
* <ul>
* <li><strong>参数：</strong> {@code node} 当前正在遍历的节点 (它是上一层 DFS 选定的起点)，{@code currentTargetSum} 是还需要累加到的目标和。</li>
* <li><strong>返回：</strong> 以 {@code node} <strong>以及其子节点</strong>向下扩展的所有路径中，和为 {@code targetSum} 的路径数量。</li>
* <li><strong>基本情况：</strong>
* <ul>
* <li>{@code if (node == null) return 0;}：如果节点为空，则没有路径，返回 0。</li>
* </ul>
* </li>
* <li><strong>核心逻辑：</strong>
* <ul>
* <li>{@code int paths = 0;}：初始化当前节点为起点查找到的路径数。</li>
* <li>{@code if (node.val == currentTargetSum)}：
* 如果当前节点的<strong>值</strong>恰好等于 {@code currentTargetSum}，说明从某个起点到当前节点正好形成了一条符合条件的路径。
* {@code paths++;}</li>
* <li>{@code paths += countPathsFromNode(node.left, currentTargetSum - node.val);}：
* 从当前节点的左子节点继续向下搜索，目标和相应减少 {@code node.val}。</li>
* <li>{@code paths += countPathsFromNode(node.right, currentTargetSum - node.val);}：
* 从当前节点的右子节点继续向下搜索，目标和相应减少 {@code node.val}。</li>
* <li>{@code return paths;}：返回以当前节点为起点向下延伸的，所有符合条件的路径总数。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N^2)}。
* <ul>
* <li>其中 {@code N} 是二叉树中的节点总数。</li>
* <li>外层 DFS 会访问每个节点一次 (N 次)。</li>
* <li>对于每个节点，内层 DFS 会从该节点向下遍历，在最坏情况下（例如，只有左子树的倾斜树）可能遍历到叶子节点，深度为 {@code H} ( H 可以是 N)。</li>
* <li>所以总的时间复杂度是 {@code N * H}，在最坏情况下为 {@code O(N^2)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public int pathSum(TreeNode root, int targetSum) {
// 如果根节点为空，则没有路径，返回 0
if (root == null) {
return 0;
}
// 以当前 root 节点为起点，找到所有路径和为 targetSum 的路径数量
int count = countPathsFromNode(root, targetSum);
// 递归计算左子树中所有节点作为起点的情况
count += pathSum(root.left, targetSum);
// 递归计算右子树中所有节点作为起点的情况
count += pathSum(root.right, targetSum);
return count;
}
/**
* 以给定节点 node 为起点，向下查找所有路径和等于 currentTargetSum 的路径数量。
*
* @param node 当前节点
* @param currentTargetSum 还需要累加到的目标和 (这里使用了 long 类型防止溢出，因为路径和可能超 Int 范围)
* @return 以 node 为起点向下延伸，路径和等于 currentTargetSum 的路径数量
*/
private int countPathsFromNode(TreeNode node, long currentTargetSum) {
// 如果节点为空，则无法形成路径，返回 0
if (node == null) {
return 0;
}
int paths = 0;
// 如果当前节点的值正好等于目标和，说明找到了一条路径
if (node.val == currentTargetSum) {
paths++;
}
// 继续在左子树中查找，目标和相应减少当前节点的值
paths += countPathsFromNode(node.left, currentTargetSum - node.val);
// 继续在右子树中查找，目标和相应减少当前节点的值
paths += countPathsFromNode(node.right, currentTargetSum - node.val);
return paths;
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}java
/**
* <p>此方法解决“路径总和 III”问题，采用<strong>前缀和 (Prefix Sum) + 哈希表 (HashMap)</strong> 的优化方法。</p>
* <p>核心思想：当从根节点到当前节点 {@code node} 路径上的累加和为 {@code currentPathSum} 时，
* 如果存在路径上的某个祖先节点，从根到该祖先节点的累加和为 {@code prefixSum}，
* 且 {@code currentPathSum - prefixSum == targetSum}，
* 那么从这个祖先节点的下一个节点到 {@code node} 的路径之和就等于 {@code targetSum}。
* 为了高效地查找这个 {@code prefixSum}，我们使用一个哈希表来存储从根节点到当前路径上所有前缀和的出现次数。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化：</strong>
* <ul>
* <li>{@code Map<Long, Integer> prefixSumCount}：哈希表，键为前缀和，值为该前缀和出现的次数。使用 {@code Long} 应对路径和可能超出 {@code Integer} 范围。</li>
* <li>{@code prefixSumCount.put(0L, 1);}：非常重要！
* <ul>
* <li>这表示在路径的起点之前（想象的空路径），累加和为 0 的情况出现了一次。</li>
* <li>它用于处理从根节点开始的路径，如果 {@code currentPathSum == targetSum}，那么 {@code currentPathSum - targetSum} 将是 {@code 0}，此时 {@code getOrDefault(0L, 0)} 会返回 1，正确统计这条路径。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>主函数 {@code pathSum(root, targetSum)}：</strong>
* <ul>
* <li>调用辅助递归函数 {@code dfs(root, 0L, targetSum, prefixSumCount)}。</li>
* </ul>
* </li>
* <li><strong>辅助递归函数 {@code dfs(node, currentPathSum, targetSum, prefixSumCount)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code node}: 当前正在遍历的节点。</li>
* <li>{@code currentPathSum}: 从根节点到 {@code node} <strong>父节点</strong>的路径和 (注意，在进入 {@code dfs} 时，{@code currentPathSum} 是到 {@code node} 父节点的和，刚开始 {@code node} 的 {@code val} 还没有加进来)。</li>
* <li>{@code targetSum}: 目标路径和。</li>
* <li>{@code prefixSumCount}: 前缀和计数哈希表。</li>
* </ul>
* </li>
* <li><strong>返回：</strong> 以 {@code node} 为根的子树中，所有符合条件的路径总数。</li>
* <li><strong>基本情况：</strong>
* <ul>
* <li>{@code if (node == null) return 0;}：如果节点为空，返回 0。</li>
* </ul>
* </li>
* <li><strong>核心逻辑：</strong>
* <ul>
* <li>{@code int count = 0;}：初始化当前节点子树中找到的路径数。</li>
* <li>{@code currentPathSum += node.val;}：更新从根节点到当前 {@code node} 的累加和。</li>
* <li>{@code count += prefixSumCount.getOrDefault(currentPathSum - targetSum, 0);}：
* <ul>
* <li>查找哈希表中是否存在一个 {@code (currentPathSum - targetSum)} 的前缀和。</li>
* <li>如果存在，其对应的次数就是从该前缀和的节点到当前 {@code node} 的路径中，和为 {@code targetSum} 的路径数量。</li>
* </ul>
* </li>
* <li>{@code prefixSumCount.put(currentPathSum, prefixSumCount.getOrDefault(currentPathSum, 0) + 1);}：
* <ul>
* <li>将当前 {@code currentPathSum} 加入哈希表（或增加其计数），以备后续子节点使用。</li>
* </ul>
* </li>
* <li>{@code count += dfs(node.left, currentPathSum, targetSum, prefixSumCount);}：递归处理左子树。</li>
* <li>{@code count += dfs(node.right, currentPathSum, targetSum, prefixSumCount);}：递归处理右子树。</li>
* <li><strong>回溯处理：</strong>
* <ul>
* <li>{@code prefixSumCount.put(currentPathSum, prefixSumCount.get(currentPathSum) - 1);}：
* 在当前节点的所有子树递归完成后，<strong>回溯时</strong>，需要将 {@code currentPathSum} 从哈希表中移除（或减少其计数）。
* 这是因为这个 {@code currentPathSum} 只对当前节点 {@code node} 及其子孙节点构成的路径有效。
* 当递归返回到 {@code node} 的父节点并转向其他分支时，{@code node} 不再是当前路径的一部分，其对应的 {@code currentPathSum} 就不应该被考虑。</li>
* </ul>
* </li>
* <li>{@code return count;}。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点只被访问一次。</li>
* <li>哈希表的插入和查找操作平均为 {@code O(1)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度和哈希表在最坏情况（倾斜树）下存储的路径和数量。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public int pathSum(TreeNode root, int targetSum) {
// 使用 HashMap 存储从根节点到当前节点路径上，所有前缀和的出现次数
// 键：前缀和，值：该前缀和出现的次数
Map<Long, Integer> prefixSumCount = new HashMap<>();
// 初始化：累加和为 0 的情况出现一次 (代表空路径的起点)
prefixSumCount.put(0L, 1);
// 调用 DFS 辅助函数，并返回结果
// 初始时 currentPathSum 为 0
return dfs(root, 0L, targetSum, prefixSumCount);
}
/**
* 深度优先搜索辅助函数，利用前缀和和哈希表来计算路径总和。
*
* @param node 当前遍历到的节点
* @param currentPathSum 从根节点到当前 node 的父节点的路径和 (不包含 node.val)
* @param targetSum 目标路径总和
* @param prefixSumCount 存储前缀和及其出现次数的哈希表
* @return 路径总和等于 targetSum 的路径数量
*/
private int dfs(TreeNode node, long currentPathSum, int targetSum, Map<Long, Integer> prefixSumCount) {
// 基本情况：如果节点为空，则返回 0
if (node == null) {
return 0;
}
int count = 0;
// 1. 更新从根节点到当前 node 的累加和
currentPathSum += node.val;
// 2. 查找是否存在一个前缀和，使得 (currentPathSum - 前缀和) 等于 targetSum
// 如果存在，说明从该前缀和对应的节点到当前 node 构成了一条符合条件的路径
// 注意：这里查找的是 (currentPathSum - targetSum)，而不是 targetSum
count += prefixSumCount.getOrDefault(currentPathSum - targetSum, 0);
// 3. 将当前 currentPathSum 加入哈希表，以便后续子节点使用
prefixSumCount.put(currentPathSum, prefixSumCount.getOrDefault(currentPathSum, 0) + 1);
// 4. 递归处理左右子树
count += dfs(node.left, currentPathSum, targetSum, prefixSumCount);
count += dfs(node.right, currentPathSum, targetSum, prefixSumCount);
// 5. 回溯：在退出当前节点时，需要撤销其对哈希表的影响
// 因为 currentPathSum 只对当前 node 及其子孙节点构成的路径有效，
// 当回溯到 node 的父节点转向其他分支时，node 就不再是当前路径的一部分了。
prefixSumCount.put(currentPathSum, prefixSumCount.get(currentPathSum) - 1);
return count;
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}二叉树的最近公共祖先
java
/**
* <p>此方法解决“二叉树的最近公共祖先”问题，采用<strong>递归深度优先搜索 (DFS)</strong> 的方式。</p>
* <p>核心思想：</p>
* <p>对于当前节点 {@code root}：</p>
*
* <ol>
* <li>如果 {@code root} 本身就是 {@code p} 或 {@code q}，那么 {@code root} 就是它们的最近公共祖先 (LCA)，因为它要么是 {@code p} 或 {@code q} 之一，要么是它们两者都在的祖先。</li>
* <li>如果在 {@code root} 的左子树中找到了 {@code p} 或 {@code q} (或它们的 LCA)，并在右子树中也找到了 {@code p} 或 {@code q} (或它们的 LCA)，那么 {@code root} 就是 {@code p} 和 {@code q} 的 LCA。</li>
* <li>如果只在左子树中找到了 {@code p} 或 {@code q} (或它们的 LCA)，而在右子树中什么也没找到，那么 LCA 就在左子树中（{@code p} 和 {@code q} 都在左子树中，或者其中一个就是 {@code root.left}，另一个在其子树中）。</li>
* <li>同理，如果只在右子树中找到了，那么 LCA 就在右子树中。</li>
* <li>如果左右子树都没有找到，那么 {@code p} 和 {@code q} 都不在以 {@code root} 为根的子树中。</li>
* </ol>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code lowestCommonAncestor(root, p, q)}：</strong> (这个函数本身就是递归函数)
* <ul>
* <li><strong>参数：</strong> {@code root} 当前节点，{@code p} 节点，{@code q} 节点。</li>
* <li><strong>返回：</strong> 在以 {@code root} 为根的子树中，{@code p} 和 {@code q} 的 LCA。如果只找到 {@code p} 或 {@code q} 中的一个，则返回找到的那个节点；如果都没找到，返回 {@code null}。</li>
* <li><strong>基本情况 (Base Case / 递归终止条件)：</strong>
* <ul>
* <li>{@code if (root == null)}：如果当前节点为空，直接返回 {@code null}。</li>
* <li>{@code if (root == p || root == q)}：如果当前节点就是 {@code p} 或 {@code q} 中的一个。
* <ul>
* <li>根据 LCA 的定义，如果其中一个节点是另一个节点的祖先，那么这个祖先就是 LCA。
* 当找到 {@code p} 或 {@code q} 时，它可能是真正的 LCA，也可能是其中一个目标节点。
* 在这种情况下，我们返回 {@code root}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>递归处理左右子树：</strong>
* <ul>
* <li>{@code TreeNode leftResult = lowestCommonAncestor(root.left, p, q);}：在左子树中查找 {@code p} 和 {@code q}。</li>
* <li>{@code TreeNode rightResult = lowestCommonAncestor(root.right, p, q);}：在右子树中查找 {@code p} 和 {@code q}。</li>
* </ul>
* </li>
* <li><strong>根据左右子树的查找结果判断：</strong>
* <ul>
* <li>{@code if (leftResult != null && rightResult != null)}：
* <ul>
* <li>这意味着 {@code p} 和 {@code q} 分别位于 {@code root} 的左子树和右子树中。</li>
* <li>因此，{@code root} 就是它们的最近公共祖先。返回 {@code root}。</li>
* </ul>
* </li>
* <li>{@code else if (leftResult != null)}：
* <ul>
* <li>这意味着 {@code p} 和 {@code q} 都存在于 {@code root} 的左子树中 (或者 {@code leftResult} 本身就是 {@code p} 或 {@code q} 之一，且另一个节点也在其左子树中)。</li>
* <li>LCA 必然在左子树中。返回 {@code leftResult}。</li>
* </ul>
* </li>
* <li>{@code else if (rightResult != null)}：
* <ul>
* <li>这意味着 {@code p} 和 {@code q} 都存在于 {@code root} 的右子树中 (或者 {@code rightResult} 本身就是 {@code p} 或 {@code q} 之一，且另一个节点也在其右子树中)。</li>
* <li>LCA 必然在右子树中。返回 {@code rightResult}。</li>
* </ul>
* </li>
* <li>{@code else} ({@code leftResult == null && rightResult == null})：
* <ul>
* <li>这意味着在 {@code root} 的左右子树中都没有找到 {@code p} 或 {@code q}。</li>
* <li>返回 {@code null}。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点最多被访问一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 基本情况：
// 1. 如果当前节点为空，则不可能找到 p 或 q，返回 null
// 2. 如果当前节点就是 p 或 q 中的一个，那么根据 LCA 的定义，
// 这个节点本身就可能是 LCA (如果另一个节点在其子树中)，
// 或者它就是目标节点之一，反正它就是目前最深的共同祖先或目标。
// 所以直接返回当前节点。
if (root == null || root == p || root == q) {
return root;
}
// 递归查找左子树中 p 和 q 的 LCA
TreeNode leftResult = lowestCommonAncestor(root.left, p, q);
// 递归查找右子树中 p 和 q 的 LCA
TreeNode rightResult = lowestCommonAncestor(root.right, p, q);
// 根据左右子树的查找结果进行判断：
// 如果左右子树都找到了结果（即 leftResult != null && rightResult != null），
// 说明 p 和 q 分别位于 root 的左右子树中。
// 这种情况下，root 就是它们的最近公共祖先。
if (leftResult != null && rightResult != null) {
return root;
}
// 如果只有左子树找到了结果 (rightResult == null)，
// 说明 p 和 q 都位于 root 的左子树中，或者 leftResult 就是 p 或 q，
// 而另一个节点也在其子树中。
// 无论哪种情况，leftResult 就是它们的 LCA。
else if (leftResult != null) {
return leftResult;
}
// 如果只有右子树找到了结果 (leftResult == null)，
// 说明 p 和 q 都位于 root 的右子树中，或者 rightResult 就是 p 或 q，
// 而另一个节点也在其子树中。
// 无论哪种情况，rightResult 就是它们的 LCA。
else if (rightResult != null) {
return rightResult;
}
// 如果左右子树都没找到任何结果 (leftResult == null && rightResult == null)，
// 说明 p 和 q 都不在以 root 为根的子树中。
// 返回 null。
else {
return null;
}
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}二叉树中的最大路径和
java
/**
* <p>此方法解决“二叉树中的最大路径和”问题，采用<strong>递归深度优先搜索 (DFS)</strong> 的方式。</p>
* <p>核心思想：
* 对于树中的任意一个节点 {@code node}，它在一条最大路径中可能有两种角色：
* 1. 作为路径的<strong>“顶点”</strong>：路径经过 {@code node}，并从 {@code node} 分别走向其左子树和右子树（但不能再往上连接父节点）。
* 这条路径的贡献是 {@code node.val + (左子树提供的最大路径增益) + (右子树提供的最大路径增益)}。
* 这种路径可以作为全局最大路径的候选。
* 2. 作为路径的<strong>“中间节点”</strong>：路径经过 {@code node}，并从 {@code node} 往上连接其父节点，同时 {@code node} 只能选择其左子树或右子树中的一个分支继续向下延伸。
* 这条路径的贡献是 {@code node.val + max((左子树提供的最大路径增益), (右子树提供的最大路径增益))}。
* 这个值将作为当前节点能为父节点提供的最大增益返回。
* <p>
* 需要注意的是，如果任何子树提供的最大路径增益是负数，那么我们不如不选择这条子路径，而是选择 0 (即不走那条分支)。
* 因此，所有从子树获取的增益都应该与 0 取最大值。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>全局变量 {@code maxSum}：</strong>
* <ul>
* <li>{@code int maxSum = Integer.MIN_VALUE;}：用于存储全局最大的路径和。初始值为 {@code Integer.MIN_VALUE}，因为节点值可以是负数，而路径至少包含一个节点。</li>
* </ul>
* </li>
* <li><strong>主函数 {@code maxPathSum(root)}：</strong>
* <ul>
* <li>初始化 {@code maxSum = Integer.MIN_VALUE;}。</li>
* <li>调用辅助递归函数 {@code maxGain(root)}。这个函数不仅计算并返回节点可以提供的最大增益，还会更新 {@code maxSum}。</li>
* <li>返回最终的 {@code maxSum}。</li>
* </ul>
* </li>
* <li><strong>辅助递归函数 {@code maxGain(node)}：</strong> (这个函数返回的是从当前节点向下走，最多延伸到一个子节点的<strong>单边路径</strong>的增益，也就是其父节点可以获得的增益)
* <ul>
* <li><strong>参数：</strong> {@code node} 当前正在处理的节点。</li>
* <li><strong>返回：</strong> 从当前 {@code node} 出发，<strong>单向向下</strong>延伸（最多选择一个子分支），能获得的最大路径和。如果这个和是负数，则返回 0（表示不选择这条路径）。</li>
* <li><strong>基本情况 (Base Case / 递归终止条件)：</strong>
* <ul>
* <li>{@code if (node == null) return 0;}：如果节点为空，不提供任何增益，返回 0。</li>
* </ul>
* </li>
* <li><strong>核心逻辑 (后序遍历思想，先处理子节点，再处理当前节点)：</strong>
* <ul>
* <li>{@code int leftGain = Math.max(0, maxGain(node.left));}：
* <ul>
* <li>递归计算左子树能为当前节点提供的最大增益。</li>
* <li>{@code Math.max(0, ...)} 表示如果左子树提供的增益是负数，就不选择它，当作贡献为 0。</li>
* </ul>
* </li>
* <li>{@code int rightGain = Math.max(0, maxGain(node.right));}：
* <ul>
* <li>同理计算右子树能为当前节点提供的最大增益。</li>
* </ul>
* </li>
* <li>{@code int currentPathSum = node.val + leftGain + rightGain;}：
* <ul>
* <li>计算<strong>以当前节点 {@code node} 为“顶点”</strong>的路径的最大和。这条路径是 {@code 左子树最大增益 -> node -> 右子树最大增益}。</li>
* <li>{@code maxSum = Math.max(maxSum, currentPathSum);}：用这个 {@code currentPathSum} <strong>更新全局的最大路径和</strong>。</li>
* </ul>
* </li>
* <li>{@code return node.val + Math.max(leftGain, rightGain);}：
* <ul>
* <li>这个返回值是当前节点 {@code node} 能够贡献给其<strong>父节点</strong>的最大路径和。
* <li>它只能选择左子树或右子树中，增益更大的那个分支，因为不能同时向上和向下两个子分支。</li>
* <li>同样需要加上 {@code node.val}。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>其中 {@code N} 是二叉树中节点的总数。每个节点都只被访问一次。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(H)}。
* <ul>
* <li>其中 {@code H} 是二叉树的高度。这是递归调用栈的最大深度。</li>
* <li>在最坏情况（例如，倾斜树），{@code H = N}，空间复杂度为 {@code O(N)}。</li>
* <li>在最好情况（例如，完全平衡树），{@code H = log_2 N}，空间复杂度为 {@code O(log N)}。</li>
* </ul>
* </li>
* </ul>
*/
// 全局变量，用于存储在整个树中找到的最大路径和
// 初始化为 Integer.MIN_VALUE，因为路径和可能包含负数节点值
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
// 调用辅助的递归函数来计算最大路径和
maxGain(root);
return maxSum;
}
/**
* 计算从当前节点 node 向下延伸的最大路径“增益”。
* 这个增益是单向的，即从 node 到其一个子树的最深路径，不能分叉。
* 同时，这个函数还会更新全局的最大路径和（考虑以 node 为顶点的路径）。
*
* @param node 当前节点
* @return 从当前节点向下延伸的最大单向路径和。如果这个和是负数，则返回 0，
* 表示不选择这条路径（因为负数会减小总和）。
*/
private int maxGain(TreeNode node) {
// 如果节点为空，则不提供任何增益，返回 0
if (node == null) {
return 0;
}
// 递归计算左右子节点的最大贡献
// 如果子树的贡献是负数，则选择 0（即不选择那条分支，将其视为没有贡献）
int leftGain = Math.max(0, maxGain(node.left));
int rightGain = Math.max(0, maxGain(node.right));
// 计算以当前 node 为“顶点”的最大路径和：
// 它的路径是：左子树提供的最大增益 + node.val + 右子树提供的最大增益
int currentPathSum = node.val + leftGain + rightGain;
// 更新全局的最大路径和
// 以 node 为顶点的路径，可能就是我们最终要找的最大路径
maxSum = Math.max(maxSum, currentPathSum);
// 返回给父节点的“增益”：
// 当前节点的值加上左右子树中较大的那个增益。
// 因为路径不能分叉，向上返回时只能选择一个子分支。
return node.val + Math.max(leftGain, rightGain);
}
// TreeNode 类的定义 (通常是题目提供的)
public static 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;
}
}贡献者
LI SIR