数据结构与算法-二叉树
前序遍历二叉树-Leetcode 144给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root =
输出：
解释：
https://i-blog.csdnimg.cn/img_convert/6f5ecb919813d4225ee220d001f7e239.png
示例 2：
输入：root =
输出：
解释：
https://i-blog.csdnimg.cn/img_convert/2a088d36e9c639263f9fb3535e58f7f5.png
示例 3：
输入：root = []
输出：[]
示例 4：
输入：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 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：
https://i-blog.csdnimg.cn/img_convert/eb8408b2b1f27629a0845c5c50138420.jpeg
<strong>输入：</strong>root =
<strong>输出：</strong>
示例 2：
<strong>输入：</strong>root = []
<strong>输出：</strong>[]
示例 3：
<strong>输入：</strong>root =
<strong>输出：</strong>/**
* 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 =
输出：
解释：
https://i-blog.csdnimg.cn/img_convert/6f5ecb919813d4225ee220d001f7e239.png
示例 2：
输入：root =
输出：
解释：
https://i-blog.csdnimg.cn/img_convert/2a088d36e9c639263f9fb3535e58f7f5.png
示例 3：
输入：root = []
输出：[]
示例 4：
输入：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 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：
https://i-blog.csdnimg.cn/img_convert/8c0249c061c3bbe784d87ab0bca10415.png
<strong>输入：</strong>root =
<strong>输出：</strong>true
示例 2：
https://i-blog.csdnimg.cn/img_convert/4869f243886f9ec373274795f7a79c93.png
<strong>输入：</strong>root =
<strong>输出：</strong>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：
https://i-blog.csdnimg.cn/img_convert/c7f39ec5da6ef191f4a8f76ed3e66b30.jpeg
<strong>输入：</strong>root =
<strong>输出：</strong>3
示例 2：
<strong>输入：</strong>root =
<strong>输出：</strong>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) {
// 如果当前节点为空，返回深度为0
if (root == null) {
return 0;
}
// 递归计算左子树的最大深度
int leftDepth = maxDepth(root.left);
// 递归计算右子树的最大深度
int rightDepth = maxDepth(root.right);
// 当前节点的深度为其左右子树最大深度加1（加上当前节点自身）
return Math.max(leftDepth, rightDepth) + 1;
}
} 二叉树最小深度-Leetcode 111
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
https://i-blog.csdnimg.cn/img_convert/4ca4d2eb70b274bc8b6da5b6c0a0e5dc.jpeg
<strong>输入：</strong>root =
<strong>输出：</strong>2
示例 2：
<strong>输入：</strong>root =
<strong>输出：</strong>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) {
// 如果当前节点为空，返回深度为0
if (root == null) {
return 0;
}
// 递归计算左子树的最小深度
int leftDepth = minDepth(root.left);
// 递归计算右子树的最小深度
int rightDepth = minDepth(root.right);
// 如果左子树或右子树有一个为空，则返回非空子树的深度加1
// 否则返回左右子树中较小的深度加1
if (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：
https://i-blog.csdnimg.cn/img_convert/a8366492aafef2426e8480231f2cc9c8.jpeg
<strong>输入：</strong>root =
<strong>输出：</strong>
示例 2：
https://i-blog.csdnimg.cn/img_convert/06bee6c566999e9a8cb80f1c9086f010.jpeg
<strong>输入：</strong>root =
<strong>输出：</strong>
示例 3：
<strong>输入：</strong>root = []
<strong>输出：</strong>[]
/**
* 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) {
// 如果当前节点为空，直接返回 null
if (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:
https://i-blog.csdnimg.cn/img_convert/d325bb50776c0ecb37fa50ca3c6fc10e.jpeg
<strong>输入</strong><strong>:</strong> preorder = , inorder =
<strong>输出:</strong>
示例 2:
<strong>输入:</strong> preorder = [-1], inorder = [-1]
<strong>输出:</strong> [-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) {
// 如果前序遍历数组为空，返回 null
if (preorder.length == 0) {
return null;
}
// 获取根节点的值（前序遍历的第一个元素）
int rootValue = preorder;
TreeNode root = new TreeNode(rootValue);
// 在中序遍历数组中找到根节点的位置
for (int i = 0; i < inorder.length; i++) {
if (inorder == 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:
https://i-blog.csdnimg.cn/img_convert/d325bb50776c0ecb37fa50ca3c6fc10e.jpeg
<strong>输入：</strong>inorder = , postorder =
<strong>输出：</strong>
示例 2:
<strong>输入：</strong>inorder = [-1], postorder = [-1]
<strong>输出：</strong>[-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) {
// 如果中序遍历数组为空，返回 null
if (inorder.length == 0) {
return null;
}
// 获取根节点的值（后序遍历的最后一个元素）
int rootValue = postorder;
TreeNode root = new TreeNode(rootValue);
// 在中序遍历数组中找到根节点的位置
int rootIndexInInorder = -1;
for (int i = 0; i < inorder.length; i++) {
if (inorder == 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;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]