前序遍历二叉树-Leetcode 144
给你二叉树的根节点
root，返回它节点值的 前序 遍历。示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
/*** Definition for a binary tree node.* public class TreeNode {* int val; // 节点的值* TreeNode left; // 左子节点* TreeNode right; // 右子节点* TreeNode() {} // 默认构造函数* TreeNode(int val) { this.val = val; } // 使用给定值初始化节点* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/*** 前序遍历二叉树的方法。* 前序遍历顺序：访问根节点 -> 遍历左子树 -> 遍历右子树** @param root 二叉树的根节点* @return 返回前序遍历的结果列表*/public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>(); // 存储前序遍历结果的列表preorder(root, result); // 调用递归方法进行前序遍历return result; // 返回前序遍历的结果}/*** 递归实现前序遍历。** @param node 当前处理的节点* @param result 用于存储遍历结果的列表*/private void preorder(TreeNode node, List<Integer> result) {if (node == null) { // 如果当前节点为空，直接返回return;}result.add(node.val); // 将当前节点的值添加到结果列表中（访问根节点）preorder(node.left, result); // 递归遍历左子树preorder(node.right, result); // 递归遍历右子树}
}中序遍历二叉树-Leetcode 94
给定一个二叉树的根节点
root，返回 它的 中序 遍历 。示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]示例 2：
输入：root = [] 输出：[]示例 3：
输入：root = [1] 输出：[1]
/*** Definition for a binary tree node.* public class TreeNode {* int val; // 节点的值* TreeNode left; // 左子节点* TreeNode right; // 右子节点* TreeNode() {} // 默认构造函数* TreeNode(int val) { this.val = val; } // 使用给定值初始化节点* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/*** 中序遍历二叉树的方法。* 中序遍历顺序：遍历左子树 -> 访问根节点 -> 遍历右子树** @param root 二叉树的根节点* @return 返回中序遍历的结果列表*/public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>(); // 存储中序遍历结果的列表inorder(root, result); // 调用递归方法进行中序遍历return result; // 返回中序遍历的结果}/*** 递归实现中序遍历。** @param node 当前处理的节点* @param result 用于存储遍历结果的列表*/private void inorder(TreeNode node, List<Integer> result) {if (node == null) { // 如果当前节点为空，直接返回return;}inorder(node.left, result); // 递归遍历左子树result.add(node.val); // 将当前节点的值添加到结果列表中（访问根节点）inorder(node.right, result); // 递归遍历右子树}
}后序遍历二叉树-Leetcode 145
给你一棵二叉树的根节点
root，返回其节点值的 后序遍历 。示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
/*** Definition for a binary tree node.* public class TreeNode {* int val; // 节点的值* TreeNode left; // 左子节点* TreeNode right; // 右子节点* TreeNode() {} // 默认构造函数* TreeNode(int val) { this.val = val; } // 使用给定值初始化节点* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/*** 后序遍历二叉树的方法。* 后序遍历顺序：遍历左子树 -> 遍历右子树 -> 访问根节点** @param root 二叉树的根节点* @return 返回后序遍历的结果列表*/public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>(); // 存储后序遍历结果的列表postorder(root, result); // 调用递归方法进行后序遍历return result; // 返回后序遍历的结果}/*** 递归实现后序遍历。** @param node 当前处理的节点* @param result 用于存储遍历结果的列表*/private void postorder(TreeNode node, List<Integer> result) {if (node == null) { // 如果当前节点为空，直接返回return;}postorder(node.left, result); // 递归遍历左子树postorder(node.right, result); // 递归遍历右子树result.add(node.val); // 将当前节点的值添加到结果列表中（访问根节点）}
}对称二叉树-Leetcode 101
给你一个二叉树的根节点
root， 检查它是否轴对称。示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
/*** Definition for a binary tree node.* public class TreeNode {* int val; // 节点的值* TreeNode left; // 左子节点* TreeNode right; // 右子节点* TreeNode() {} // 默认构造函数* TreeNode(int val) { this.val = val; } // 使用给定值初始化节点* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/*** 检查二叉树是否对称。* 对称的定义是：左子树和右子树互为镜像。** @param root 二叉树的根节点* @return 如果树是对称的返回 true，否则返回 false*/public boolean isSymmetric(TreeNode root) {// 如果根节点为空，则认为是对称的if (root == null) {return true;}// 检查根节点的左子树和右子树是否对称return check(root.left, root.right);}/*** 递归检查两个子树是否互为镜像。** @param left 当前处理的左子树的根节点* @param right 当前处理的右子树的根节点* @return 如果两棵子树互为镜像返回 true，否则返回 false*/public boolean check(TreeNode left, TreeNode right) {// 如果两个节点都为空，则它们是对称的if (left == null && right == null) {return true;}// 如果其中一个节点为空而另一个不为空，则它们不对称if (left == null || right == null) {return false;}// 如果两个节点的值不同，则它们不对称if (left.val != right.val) {return false;}// 递归检查：// 左子树的左子节点和右子树的右子节点是否对称// 左子树的右子节点和右子树的左子节点是否对称return check(left.left, right.right) && check(left.right, right.left);}
}二叉树最大深度-Leetcode 104
给定一个二叉树
root，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3示例 2：
输入：root = [1,null,2] 输出：2
/*** Definition for a binary tree node.* public class TreeNode {* int val; // 节点的值* TreeNode left; // 左子节点* TreeNode right; // 右子节点* TreeNode() {} // 默认构造函数* TreeNode(int val) { this.val = val; } // 使用给定值初始化节点* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/*** 计算二叉树的最大深度。* 最大深度是从根节点到最远叶子节点的最长路径上的节点数。** @param root 二叉树的根节点* @return 返回二叉树的最大深度*/public int maxDepth(TreeNode root) {// 如果当前节点为空，返回深度为0if (root == null) {return 0;}// 递归计算左子树的最大深度int leftDepth = maxDepth(root.left);// 递归计算右子树的最大深度int rightDepth = maxDepth(root.right);// 当前节点的深度为其左右子树最大深度加1（加上当前节点自身）return Math.max(leftDepth, rightDepth) + 1;}
}二叉树最小深度-Leetcode 111
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
/*** Definition for a binary tree node.* public class TreeNode {* int val; // 节点的值* TreeNode left; // 左子节点* TreeNode right; // 右子节点* TreeNode() {} // 默认构造函数* TreeNode(int val) { this.val = val; } // 使用给定值初始化节点* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/*** 计算二叉树的最小深度。* 最小深度是从根节点到最近的叶子节点的最短路径上的节点数。** @param root 二叉树的根节点* @return 返回二叉树的最小深度*/public int minDepth(TreeNode root) {// 如果当前节点为空，返回深度为0if (root == null) {return 0;}// 递归计算左子树的最小深度int leftDepth = minDepth(root.left);// 递归计算右子树的最小深度int rightDepth = minDepth(root.right);// 如果左子树或右子树有一个为空，则返回非空子树的深度加1// 否则返回左右子树中较小的深度加1if (leftDepth == 0 && rightDepth == 0) {return 1; // 当前节点是叶子节点} else if (leftDepth == 0) {return rightDepth + 1;} else if (rightDepth == 0) {return leftDepth + 1;} else {return Math.min(leftDepth, rightDepth) + 1;}}
}翻转二叉树-Leetcode 226
给你一棵二叉树的根节点
root，翻转这棵二叉树，并返回其根节点。示例 1：
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]示例 2：
输入：root = [2,1,3] 输出：[2,3,1]示例 3：
输入：root = [] 输出：[]
/*** Definition for a binary tree node.* public class TreeNode {* int val; // 节点的值* TreeNode left; // 左子节点* TreeNode right; // 右子节点* TreeNode() {} // 默认构造函数* TreeNode(int val) { this.val = val; } // 使用给定值初始化节点* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/*** 翻转二叉树。* 对于每个节点，交换其左子树和右子树。** @param root 二叉树的根节点* @return 返回翻转后的二叉树的根节点*/public TreeNode invertTree(TreeNode root) {// 如果当前节点为空，直接返回 nullif (root == null) {return null;}// 递归翻转左子树TreeNode left = invertTree(root.left);// 递归翻转右子树TreeNode right = invertTree(root.right);// 交换当前节点的左子树和右子树TreeNode temp = root.left;root.left = root.right;root.right = temp;// 返回当前节点（翻转后的子树的根节点）return root;}
}根据前序与中序遍历结果构造二叉树-Leetcode 105
给定两个整数数组
preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]
import java.util.Arrays;/*** Definition for a binary tree node.* public class TreeNode {* int val; // 节点的值* TreeNode left; // 左子节点* TreeNode right; // 右子节点* TreeNode() {} // 默认构造函数* TreeNode(int val) { this.val = val; } // 使用给定值初始化节点* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/*** 根据前序遍历和中序遍历数组重建二叉树。** @param preorder 前序遍历数组* @param inorder 中序遍历数组* @return 返回重建后的二叉树的根节点*/public TreeNode buildTree(int[] preorder, int[] inorder) {// 如果前序遍历数组为空，返回 nullif (preorder.length == 0) {return null;}// 获取根节点的值（前序遍历的第一个元素）int rootValue = preorder[0];TreeNode root = new TreeNode(rootValue);// 在中序遍历数组中找到根节点的位置for (int i = 0; i < inorder.length; i++) {if (inorder[i] == rootValue) {// 分割中序遍历数组为左子树和右子树部分int[] inLeft = Arrays.copyOfRange(inorder, 0, i);int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);// 分割前序遍历数组为左子树和右子树部分int[] preLeft = Arrays.copyOfRange(preorder, 1, i + 1);int[] preRight = Arrays.copyOfRange(preorder, i + 1, inorder.length);// 递归构建左子树和右子树root.left = buildTree(preLeft, inLeft);root.right = buildTree(preRight, inRight);break; // 找到根节点后跳出循环}}// 返回重建后的根节点return root;}
}根据中序与后序遍历结果构造二叉树-Leetcode 106
给定两个整数数组
inorder和postorder，其中inorder是二叉树的中序遍历，postorder是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]示例 2:
输入：inorder = [-1], postorder = [-1] 输出：[-1]
import java.util.Arrays;/*** Definition for a binary tree node.* public class TreeNode {* int val; // 节点的值* TreeNode left; // 左子节点* TreeNode right; // 右子节点* TreeNode() {} // 默认构造函数* TreeNode(int val) { this.val = val; } // 使用给定值初始化节点* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/*** 根据中序遍历和后序遍历数组重建二叉树。** @param inorder 中序遍历数组* @param postorder 后序遍历数组* @return 返回重建后的二叉树的根节点*/public TreeNode buildTree(int[] inorder, int[] postorder) {// 如果中序遍历数组为空，返回 nullif (inorder.length == 0) {return null;}// 获取根节点的值（后序遍历的最后一个元素）int rootValue = postorder[postorder.length - 1];TreeNode root = new TreeNode(rootValue);// 在中序遍历数组中找到根节点的位置int rootIndexInInorder = -1;for (int i = 0; i < inorder.length; i++) {if (inorder[i] == rootValue) {rootIndexInInorder = i;break;}}// 分割中序遍历数组为左子树和右子树部分int[] inLeft = Arrays.copyOfRange(inorder, 0, rootIndexInInorder);int[] inRight = Arrays.copyOfRange(inorder, rootIndexInInorder + 1, inorder.length);// 分割后序遍历数组为左子树和右子树部分int[] postLeft = Arrays.copyOfRange(postorder, 0, rootIndexInInorder);int[] postRight = Arrays.copyOfRange(postorder, rootIndexInInorder, postorder.length - 1);// 递归构建左子树和右子树root.left = buildTree(inLeft, postLeft);root.right = buildTree(inRight, postRight);// 返回重建后的根节点return root;}
}
