1. 二叉树的最大深度
问题：计算二叉树的最大深度（或高度）。
Java 实现：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
2. 二叉树的最小深度
问题：计算二叉树的最小深度，即从根节点到最接近的叶子节点的路径长度。
Java 实现：
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int leftDepth = root.left != null ? minDepth(root.left) : Integer.MAX_VALUE;
int rightDepth = root.right != null ? minDepth(root.right) : Integer.MAX_VALUE;
return Math.min(leftDepth, rightDepth) + 1;
}
}
3. 二叉树的层序遍历
问题：返回二叉树的层序遍历结果（即每一层的节点从左到右的顺序）。
Java 实现：
import java.util.*;
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
result.add(currentLevel);
}
return result;
}
}
4. 判断二叉树是否对称
问题：检查一个二叉树是否是对称的（即它的左右子树是否镜像对称）。
Java 实现：
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null) {
return false;
}
return (t1.val == t2.val) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right);
}
}
5. 二叉树的最大路径和
问题：找到二叉树中的最大路径和。路径可以从任意节点开始，也可以到达任意节点。
Java 实现：
public class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathSumHelper(root);
return maxSum;
}
private int maxPathSumHelper(TreeNode node) {
if (node == null) {
return 0;
}
int left = Math.max(maxPathSumHelper(node.left), 0);
int right = Math.max(maxPathSumHelper(node.right), 0);
maxSum = Math.max(maxSum, left + right + node.val);
return Math.max(left, right) + node.val;
}
}
6. 二叉树的路径总和
问题：给定一个目标和，判断二叉树中是否存在一条从根节点到叶子节点的路径，其路径和等于目标和。
Java 实现：
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return root.val == sum;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
7. 二叉树的翻转
问题：翻转二叉树（交换每个节点的左右子树）。
Java 实现：
public 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;
}
}
8. 验证二叉搜索树
问题：验证一个二叉树是否是有效的二叉搜索树（BST）。
Java 实现：
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode node, long min, long max) {
if (node == null) {
return true;
}
if (node.val <= min || node.val >= max) {
return false;
}
return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
}
}
9. 二叉树的最近公共祖先
问题：给定二叉树中的两个节点，找到它们的最近公共祖先（LCA）。
Java 实现：
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}
10. 将有序数组转换为二叉搜索树
问题：给定一个有序数组，将其转换为一棵高度平衡的二叉搜索树（BST）。
Java 实现：
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBST(nums, 0, nums.length - 1);
}
private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
if (start > end) {
return null;
}
int mid = (start + end) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = sortedArrayToBST(nums, start, mid - 1);
node.right = sortedArrayToBST(nums, mid + 1, end);
return node;
}
}
11. 根据前序遍历和中序遍历构建二叉树
问题：给定前序遍历和中序遍历结果，重建二叉树。
Java 实现：
import java.util.HashMap;
import java.util.Map;
public class Solution {
private Map<Integer, Integer> inorderIndexMap;
private int preorderIndex;
public TreeNode buildTree(int[] preorder, int[] inorder) {
inorderIndexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderIndexMap.put(inorder[i], i);
}
preorderIndex = 0;
return buildTree(preorder, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int left, int right) {
if (left > right) {
return null;
}
int rootValue = preorder[preorderIndex++];
TreeNode root = new TreeNode(rootValue);
int inorderIndex = inorderIndexMap.get(rootValue);
root.left = buildTree(preorder, left, inorderIndex - 1);
root.right = buildTree(preorder, inorderIndex + 1, right);
return root;
}
}
12. 二叉树的所有路径
问题：给定一个二叉树，返回从根节点到所有叶子节点的路径。
Java 实现：
import java.util.*;
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
if (root != null) {
findPaths(root, "", paths);
}
return paths;
}
private void findPaths(TreeNode node, String path, List<String> paths) {
if (node.left == null && node.right == null) {
paths.add(path + node.val);
} else {
if (node.left != null) {
findPaths(node.left, path + node.val + "->", paths);
}
if (node.right != null) {
findPaths(node.right, path + node.val + "->", paths);
}
}
}
}
13. 二叉树的直径
问题：计算二叉树的直径，即二叉树中任意两个节点之间的最长路径的长度。
Java 实现：
public class Solution {
private int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return diameter;
}
private int depth(TreeNode node) {
if (node == null) {
return 0;
}
int leftDepth = depth(node.left);
int rightDepth = depth(node.right);
diameter = Math.max(diameter, leftDepth + rightDepth);
return Math.max(leftDepth, rightDepth) + 1;
}
}
14. 判断两个树是否相同
问题：检查两个二叉树是否相同，即它们的结构和节点值是否完全一致。
Java 实现：
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return (p.val == q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
15. 二叉树的右视图
问题：返回二叉树从右侧看到的节点值列表。
Java 实现：
import java.util.*;
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (i == levelSize - 1) {
result.add(node.val);
}
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}
return result;
}
}
16. 二叉树的层次遍历
问题：返回二叉树的层次遍历结果，其中每一层的节点值都放在一个列表中。
Java 实现：
import java.util.*;
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
result.add(level);
}
return result;
}
}
17. 从前序和后序遍历构建二叉树
问题：给定前序遍历和后序遍历的结果，构建二叉树。
Java 实现：
public class Solution {
private Map<Integer, Integer> postorderIndexMap;
private int preorderIndex;
public TreeNode buildTree(int[] preorder, int[] postorder) {
postorderIndexMap = new HashMap<>();
for (int i = 0; i < postorder.length; i++) {
postorderIndexMap.put(postorder[i], i);
}
preorderIndex = 0;
return buildTree(preorder, 0, postorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int left, int right) {
if (left > right) {
return null;
}
TreeNode root = new TreeNode(preorder[preorderIndex++]);
if (left == right) {
return root;
}
int postorderIndex = postorderIndexMap.get(preorder[preorderIndex]);
root.left = buildTree(preorder, left, postorderIndex - 1);
root.right = buildTree(preorder, postorderIndex + 1, right);
return root;
}
}
18. 将二叉搜索树转换为排序双向链表
问题：将一棵二叉搜索树（BST）转换为一个排序的双向链表，并返回链表的头节点。
Java 实现：
public class Solution {
private TreeNode lastNode = null;
private TreeNode head = null;
public TreeNode convertBSTToDoublyList(TreeNode root) {
if (root == null) {
return null;
}
inOrder(root);
return head;
}
private void inOrder(TreeNode node) {
if (node == null) {
return;
}
inOrder(node.left);
if (lastNode == null) {
head = node;
} else {
lastNode.right = node;
node.left = lastNode;
}
lastNode = node;
inOrder(node.right);
}
}
19. 恢复二叉搜索树
问题：给定一个二叉搜索树，其中两个节点的值被错误地交换，恢复树使其成为有效的二叉搜索树。
Java 实现：
public class Solution {
private TreeNode first = null;
private TreeNode second = null;
private TreeNode prev = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
inorderTraversal(root);
if (first != null && second != null) {
int temp = first.val;
first.val = second.val;
second.val = temp;
}
}
private void inorderTraversal(TreeNode node) {
if (node == null) {
return;
}
inorderTraversal(node.left);
if (first == null && prev.val >= node.val) {
first = prev;
}
if (first != null && prev.val >= node.val) {
second = node;
}
prev = node;
inorderTraversal(node.right);
}
}
20. 将二叉树转化为链表
问题：将二叉树转换为一个“链表”，链表的每个节点都是二叉树的节点，并且节点的顺序应该是按前序遍历的顺序。
Java 实现：
public class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
flattenTree(root);
}
private TreeNode flattenTree(TreeNode node) {
if (node == null) {
return null;
}
TreeNode left = flattenTree(node.left);
TreeNode right = flattenTree(node.right);
if (left != null) {
TreeNode rightMost = left;
while (rightMost.right != null) {
rightMost = rightMost.right;
}
rightMost.right = right;
node.right = left;
node.left = null;
} else {
node.right = right;
node.left = null;
}
return node;
}
}
21. 判断二叉树是否为子树
问题：检查一个二叉树是否为另一个二叉树的子树。
Java 实现：
public class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return false;
}
if (isSameTree(root, subRoot)) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean isSameTree(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null) {
return false;
}
return (t1.val == t2.val) && isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);
}
}
22. 二叉树的最大路径和（以任意节点为起点）
问题：找到二叉树中从任意节点开始到任意节点结束的最大路径和（不同于之前的最大路径和，它允许从树中间的节点开始和结束）。
Java 实现：
public class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathSumHelper(root);
return maxSum;
}
private int maxPathSumHelper(TreeNode node) {
if (node == null) {
return 0;
}
int left = Math.max(maxPathSumHelper(node.left), 0);
int right = Math.max(maxPathSumHelper(node.right), 0);
maxSum = Math.max(maxSum, left + right + node.val);
return Math.max(left, right) + node.val;
}
}
23. 二叉树的所有根到叶子路径
问题：返回所有从根节点到叶子节点的路径，每条路径的节点值用“->”连接。
Java 实现：
import java.util.*;
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
if (root != null) {
buildPaths(root, "", paths);
}
return paths;
}
private void buildPaths(TreeNode node, String path, List<String> paths) {
if (node.left == null && node.right == null) {
paths.add(path + node.val);
} else {
if (node.left != null) {
buildPaths(node.left, path + node.val + "->", paths);
}
if (node.right != null) {
buildPaths(node.right, path + node.val + "->", paths);
}
}
}
}
24. 平衡二叉树
问题：检查二叉树是否为平衡二叉树，即每个节点的左右子树的高度差不超过1。
Java 实现：
public class Solution {
public boolean isBalanced(TreeNode root) {
return checkHeight(root) != -1;
}
private int checkHeight(TreeNode node) {
if (node == null) {
return 0;
}
int leftHeight = checkHeight(node.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = checkHeight(node.right);
if (rightHeight == -1) {
return -1;
}
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
}
25. 二叉树的最小公共祖先
问题：找到二叉树中两个节点的最小公共祖先（LCA），如果树中存在重复的节点，需要考虑每个节点可能对应不同的 LCA。
Java 实现：
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}
26. 二叉树的前序、中序、后序遍历
问题：实现二叉树的前序遍历、中序遍历和后序遍历。
Java 实现：
import java.util.*;
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorder(root, result);
return result;
}
private void preorder(TreeNode node, List<Integer> result) {
if (node != null) {
result.add(node.val);
preorder(node.left, result);
preorder(node.right, result);
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
private void inorder(TreeNode node, List<Integer> result) {
if (node != null) {
inorder(node.left, result);
result.add(node.val);
inorder(node.right, result);
}
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorder(root, result);
return result;
}
private void postorder(TreeNode node, List<Integer> result) {
if (node != null) {
postorder(node.left, result);
postorder(node.right, result);
result.add(node.val);
}
}
}
27. 二叉树的最大宽度
问题：计算二叉树每一层的宽度，并返回最大宽度。
Java 实现：
import java.util.*;
public class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
int maxWidth = 0;
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> indexQueue = new LinkedList<>();
queue.add(root);
indexQueue.add(0);
while (!queue.isEmpty()) {
int levelSize = queue.size();
int minIndex = indexQueue.peek();
int first = 0, last = 0;
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
int index = indexQueue.poll();
if (i == 0) first = index;
if (i == levelSize - 1) last = index;
if (node.left != null) {
queue.add(node.left);
indexQueue.add(2 * index);
}
if (node.right != null) {
queue.add(node.right);
indexQueue.add(2 * index + 1);
}
}
maxWidth = Math.max(maxWidth, last - first + 1);
}
return maxWidth;
}
}
28. 二叉树的镜像
问题：对二叉树进行镜像翻转，即将二叉树的左右子树交换。
Java 实现：
public class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = mirrorTree(root.left);
TreeNode right = mirrorTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
29. 二叉树的范围和
问题：给定一个范围 [low, high]，计算二叉树中所有节点值在此范围内的节点值的和。
Java 实现：
public class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
if (root == null) {
return 0;
}
int sum = 0;
if (root.val >= low && root.val <= high) {
sum += root.val;
}
if (root.val > low) {
sum += rangeSumBST(root.left, low, high);
}
if (root.val < high) {
sum += rangeSumBST(root.right, low, high);
}
return sum;
}
}
30. 二叉树的垂直遍历
问题：返回二叉树的垂直遍历结果。节点按列从左到右，从上到下的顺序排列。
Java 实现：
import java.util.*;
public class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
Map<Integer, List<Integer>> map = new TreeMap<>();
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> columnQueue = new LinkedList<>();
if (root == null) {
return new ArrayList<>();
}
queue.add(root);
columnQueue.add(0);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int column = columnQueue.poll();
map.computeIfAbsent(column, x -> new ArrayList<>()).add(node.val);
if (node.left != null) {
queue.add(node.left);
columnQueue.add(column - 1);
}
if (node.right != null) {
queue.add(node.right);
columnQueue.add(column + 1);
}
}
return new ArrayList<>(map.values());
}
}
31. 二叉树的深度
问题：计算二叉树的深度或高度，即从根节点到最深叶子节点的最长路径的长度。
Java 实现：
public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
32. 二叉树的节点数量
问题：计算二叉树中的节点总数。
Java 实现：
public class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
33. 二叉树的叶子节点
问题：找出二叉树中的所有叶子节点（没有子节点的节点）。
Java 实现：
import java.util.*;
public class Solution {
public List<Integer> leafNodes(TreeNode root) {
List<Integer> leaves = new ArrayList<>();
findLeaves(root, leaves);
return leaves;
}
private void findLeaves(TreeNode node, List<Integer> leaves) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
leaves.add(node.val);
} else {
findLeaves(node.left, leaves);
findLeaves(node.right, leaves);
}
}
}
34. 判断二叉树是否为完全二叉树
问题：判断一个二叉树是否为完全二叉树，即除了最后一层外，每一层的节点数都达到最大，并且最后一层的节点集中在左侧。
Java 实现：
import java.util.*;
public class Solution {
public boolean isCompleteBinaryTree(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean end = false;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
end = true;
} else {
if (end) {
return false;
}
queue.add(node.left);
queue.add(node.right);
}
}
return true;
}
}
35. 二叉树的镜像对称
问题：判断二叉树是否是镜像对称的，即它与它自身的镜像是否相同。
Java 实现：
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null) {
return false;
}
return (t1.val == t2.val) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right);
}
}
36. 二叉树的倒序遍历
问题：对二叉树进行倒序遍历，即先遍历右子树，再遍历左子树。
Java 实现：
import java.util.*;
public class Solution {
public List<Integer> reverseOrderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
reverseOrder(root, result);
return result;
}
private void reverseOrder(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
reverseOrder(node.right, result);
result.add(node.val);
reverseOrder(node.left, result);
}
}
37. 平衡二叉树的最小深度
问题：找到二叉树的最小深度，即从根节点到最近的叶子节点的路径长度。
Java 实现：
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int minDepth = Integer.MAX_VALUE;
if (root.left != null) {
minDepth = Math.min(minDepth, minDepth(root.left));
}
if (root.right != null) {
minDepth = Math.min(minDepth, minDepth(root.right));
}
return minDepth + 1;
}
}
38. 二叉树的路径总和（从根到叶子的路径）
问题：计算二叉树中所有从根到叶子节点的路径的节点值的总和。
Java 实现：
public class Solution {
public int sumOfLeafNodes(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return root.val;
}
return sumOfLeafNodes(root.left) + sumOfLeafNodes(root.right);
}
}
39. 二叉树的相同子树
问题：找到二叉树中所有相同的子树，并返回这些子树的根节点。
Java 实现：
import java.util.*;
public class Solution {
private Map<String, Integer> map = new HashMap<>();
private List<TreeNode> result = new ArrayList<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
serialize(root);
return result;
}
private String serialize(TreeNode node) {
if (node == null) {
return "#";
}
String left = serialize(node.left);
String right = serialize(node.right);
String serialized = left + "," + right + "," + node.val;
if (map.getOrDefault(serialized, 0) == 1) {
result.add(node);
}
map.put(serialized, map.getOrDefault(serialized, 0) + 1);
return serialized;
}
}
40. 二叉树的所有路径（从任意节点开始）
问题：找出从任意节点开始到所有其他节点的路径。
Java 实现：
import java.util.*;
public class Solution {
public List<List<Integer>> allPathsFromAnyNode(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
List<Integer> path = new ArrayList<>();
allPathsFromAnyNode(root, path, result);
return result;
}
private void allPathsFromAnyNode(TreeNode node, List<Integer> path, List<List<Integer>> result) {
if (node == null) {
return;
}
path.add(node.val);
result.add(new ArrayList<>(path));
allPathsFromAnyNode(node.left, path, result);
allPathsFromAnyNode(node.right, path, result);
path.remove(path.size() - 1);
}
}
41. 二叉树的层次遍历（带深度）
问题：对二叉树进行层次遍历，同时返回每个节点的深度。
Java 实现：
import java.util.*;
public class Solution {
public List<List<Integer>> levelOrderWithDepth(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> depthQueue = new LinkedList<>();
queue.add(root);
depthQueue.add(0);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>();
int depth = depthQueue.peek();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
int currentDepth = depthQueue.poll();
if (currentDepth == depth) {
level.add(node.val);
}
if (node.left != null) {
queue.add(node.left);
depthQueue.add(currentDepth + 1);
}
if (node.right != null) {
queue.add(node.right);
depthQueue.add(currentDepth + 1);
}
}
result.add(level);
}
return result;
}
}
42. 二叉树的直径（包含路径）
问题：计算二叉树的直径，并返回直径路径的节点值。
Java 实现：
import java.util.*;
public class Solution {
private int diameter = 0;
private List<Integer> path = new ArrayList<>();
public List<Integer> diameterOfBinaryTree(TreeNode root) {
List<Integer> result = new ArrayList<>();
findDiameter(root);
getPath(root, result);
return result;
}
private int findDiameter(TreeNode node) {
if (node == null) {
return 0;
}
int leftDepth = findDiameter(node.left);
int rightDepth = findDiameter(node.right);
diameter = Math.max(diameter, leftDepth + rightDepth);
return Math.max(leftDepth, rightDepth) + 1;
}
private void getPath(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val);
if (path.size() == diameter) {
return;
}
if (node.left != null && (findDiameter(node.left) + findDiameter(node.right) == diameter)) {
getPath(node.left, result);
} else if (node.right != null && (findDiameter(node.left) + findDiameter(node.right) == diameter)) {
getPath(node.right, result);
}
}
}
43. 二叉树的所有路径（包含目标值）
问题：返回所有从根节点到叶子节点的路径，并计算每条路径的和是否等于目标值。
Java 实现：
import java.util.*;
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
findPaths(root, targetSum, path, result);
return result;
}
private void findPaths(TreeNode node, int targetSum, List<Integer> path, List<List<Integer>> result) {
if (node == null) {
return;
}
path.add(node.val);
if (node.left == null && node.right == null && node.val == targetSum) {
result.add(new ArrayList<>(path));
} else {
findPaths(node.left, targetSum - node.val, path, result);
findPaths(node.right, targetSum - node.val, path, result);
}
path.remove(path.size() - 1);
}
}
44. 二叉树的路径和
问题：计算二叉树中所有路径的和，其中路径可以是从根到叶子节点，也可以是从任何节点到任何其他节点。
Java 实现：
public class Solution {
public int pathSum(TreeNode root) {
return pathSumFromRoot(root) + pathSumFromChildren(root);
}
private int pathSumFromRoot(TreeNode node) {
if (node == null) {
return 0;
}
int sum = node.val;
sum += pathSumFromRoot(node.left);
sum += pathSumFromRoot(node.right);
return sum;
}
private int pathSumFromChildren(TreeNode node) {
if (node == null) {
return 0;
}
return pathSumFromRoot(node.left) + pathSumFromRoot(node.right)
+ pathSumFromChildren(node.left) + pathSumFromChildren(node.right);
}
}
45. 二叉树的根到所有节点的路径
问题：找出从根节点到每个节点的路径。
Java 实现：
import java.util.*;
public class Solution {
public List<List<Integer>> pathsFromRoot(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
findPaths(root, path, result);
return result;
}
private void findPaths(TreeNode node, List<Integer> path, List<List<Integer>> result) {
if (node == null) {
return;
}
path.add(node.val);
if (node.left == null && node.right == null) {
result.add(new ArrayList<>(path));
} else {
findPaths(node.left, path, result);
findPaths(node.right, path, result);
}
path.remove(path.size() - 1);
}
}
46. 二叉树的对称子树
问题：找出二叉树中所有对称的子树，并返回这些子树的根节点。
Java 实现：
import java.util.*;
public class Solution {
private List<TreeNode> result = new ArrayList<>();
public List<TreeNode> findSymmetricSubtrees(TreeNode root) {
findSymmetric(root);
return result;
}
private boolean findSymmetric(TreeNode node) {
if (node == null) {
return true;
}
boolean isSymmetric = isMirror(node.left, node.right);
if (isSymmetric) {
result.add(node);
}
findSymmetric(node.left);
findSymmetric(node.right);
return isSymmetric;
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null) {
return false;
}
return (t1.val == t2.val) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right);
}
}
47. 二叉树的最小公共祖先（节点值）
问题：找到二叉树中两个节点的最小公共祖先，并返回祖先节点的值。
Java 实现：
public class Solution {
public Integer lowestCommonAncestorValue(TreeNode root, TreeNode p, TreeNode q) {
TreeNode lca = lowestCommonAncestor(root, p, q);
return lca != null ? lca.val : null;
}
private TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}
48. 二叉树的路径和（从任意节点到任意节点）
问题：计算从任意节点到任意节点的所有路径的和（注意这包括了从根到任何节点的路径）。
Java 实现：
public class Solution {
private int maxSum = Integer.MIN_VALUE;
public int maxPathSumAnyToAny(TreeNode root) {
maxPathSumFromAnyNode(root);
return maxSum;
}
private int maxPathSumFromAnyNode(TreeNode node) {
if (node == null) {
return 0;
}
int left = Math.max(maxPathSumFromAnyNode(node.left), 0);
int right = Math.max(maxPathSumFromAnyNode(node.right), 0);
maxSum = Math.max(maxSum, left + right + node.val);
return Math.max(left, right) + node.val;
}
}
49. 二叉树的路径节点
问题：找出所有从根节点到叶子节点的路径，并返回这些路径的节点列表。
Java 实现：
import java.util.*;
public class Solution {
public List<List<TreeNode>> allPaths(TreeNode root) {
List<List<TreeNode>> result = new ArrayList<>();
List<TreeNode> path =
new ArrayList<>();
findAllPaths(root, path, result);
return result;
}
private void findAllPaths(TreeNode node, List<TreeNode> path, List<List<TreeNode>> result) {
if (node == null) {
return;
}
path.add(node);
if (node.left == null && node.right == null) {
result.add(new ArrayList<>(path));
} else {
findAllPaths(node.left, path, result);
findAllPaths(node.right, path, result);
}
path.remove(path.size() - 1);
}
}
50. 二叉树的路径节点（从任意节点到任意节点）
问题：找出所有从任意节点到任意节点的路径。
Java 实现：
import java.util.*;
public class Solution {
public List<List<TreeNode>> allPathsFromAnyNode(TreeNode root) {
List<List<TreeNode>> result = new ArrayList<>();
findAllPathsFromAnyNode(root, result);
return result;
}
private void findAllPathsFromAnyNode(TreeNode node, List<List<TreeNode>> result) {
if (node == null) {
return;
}
List<TreeNode> path = new ArrayList<>();
findPathsFromNode(node, path, result);
findAllPathsFromAnyNode(node.left, result);
findAllPathsFromAnyNode(node.right, result);
}
private void findPathsFromNode(TreeNode node, List<TreeNode> path, List<List<TreeNode>> result) {
if (node == null) {
return;
}
path.add(node);
result.add(new ArrayList<>(path));
findPathsFromNode(node.left, path, result);
findPathsFromNode(node.right, path, result);
path.remove(path.size() - 1);
}
}