二叉树
2025/5/19大约 6 分钟
二叉树
二叉树的中序遍历
力扣题目连接：二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
[](https://imgse.com/i/pEvxvj0)
输入：root = [1,null,2,3]
输出：[1,3,2]示例 2：
输入：root = []
输出：[]示例 3：
输入：root = [1]
输出：[1]/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> result;
void dfs(TreeNode *root){//这个题目算是比较简单的递归了
if(root==nullptr){return;}
dfs(root->left);
result.push_back(root->val);
dfs(root->right);
}
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return result;
}
};二叉树的最大深度
二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
思路一：递归实现，传入根节点所在树的最大深度等于左右子树最大深度的较大值加1，依次递归，知道根节点为空，返回0
/**
* 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 {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}else{
int maxLeft = maxDepth(root.left);
int maxRight = maxDepth(root.right);
return Math.max(maxLeft,maxRight) + 1;
}
}
}思路二：BFS迭代实现，使用队列，将根节点入队，同时定义一个变量记录当前层数，当队列不为空时，将队列中的节点出队，并判断当前节点的左右子节点是否为空，如果不为空，则将左右子节点入队，同时层数加1，直到队列为空，返回层数。注意这里要定义一个size记录当前层的节点数，因为每层节点数都会改变，所以不能使用队列的长度来判断当前层是否遍历完。
/**
* 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 {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
// 创建队列
Queue<TreeNode> queue = new LinkedList<TreeNode>();
// 根节点入队
queue.add(root);
// 定义层数
int res = 0;
// 循环队列,当队列为空时表示各层各节点都遍历完
while(!queue.isEmpty()){
// 获取当前层的节点数，每一层节点数都会改变，不能使用队列的长度来判断当前层是否遍历完
int size = queue.size();
// 遍历当前层的节点
while(size > 0){
TreeNode node = queue.poll();
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
size--;
}
res++;
}
return res;
}
}反转二叉树
反转二叉树、
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例一：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例二：
输入：root = [2,1,3]
输出：[2,3,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 {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.right = left;
root.left = right;
return root;
}
}思路二：BFS迭代，使用队列，将根节点入队，当队列不为空时，将队列中的节点出队，并交换左右子节点，将左右子节点入队，直到队列为空，返回根节点。
/**
* 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 {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
TreeNode leftNode = node.left;
TreeNode rightNode = node.right;
node.left = rightNode;
node.right = leftNode;
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
return root;
}
}对称二叉树
对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例一：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例二：
输入：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 {
public boolean isSymmetric(TreeNode root) {
return check(root.left, root.right);
}
public boolean check(TreeNode left, TreeNode right){
// 如果左右子树都为空，则对称
if(left == null && right == null){
return true;
// 如果左右子树只有一个为空，则不对称
}else if(left == null || right == null){
return false;
}
// 如果左右子树的根节点值不相等，则不对称，并且递归判断左右子树的左右子树是否对称
return left.val == right.val && check(left.left,right.right) && check(left.right,right.left);
}
}思路二：BFS迭代，使用队列，将根节点的左右子节点入队，当队列不为空时，将队列中的节点出队，并判断左右子节点是否相等，将左右子节点的左右子节点入队，直到队列为空，返回结果。
/**
* 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 {
public boolean isSymmetric(TreeNode root) {
// 这个判断用来对root做一次判断，也可以直接最开始就在queue中传入两个root，这样的话判断就在while中进行了，但是这样的话两个根节点都要判断，这样会重复判断
// 如果根节点的左右子节点都为空，则对称
if(root.left == null && root.right == null){
return true;
// 如果根节点的左右子节点只有一个为空，则不对称
}else if(root.left == null || root.right == null){
return false;
}
//
Queue<TreeNode> queue =new LinkedList<TreeNode>();
queue.add(root.left);
queue.add(root.right);
while(!queue.isEmpty()){
TreeNode p = queue.poll();
TreeNode q = queue.poll();
if(p == null && q == null){
continue;
}else if((q == null || p == null) || p.val != q.val ){
return false;
}
queue.add(p.left);
queue.add(q.right);
queue.add(p.right);
queue.add(q.left);
}
return true;
}
}二叉树的直径
二叉树的直径
给定一个二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例：
输入：root = [1,2,3,4,5]
输出：3
思路：使用递归，计算左右子树的高度，并返回左右子树的高度之和(即以该节点为根节点的树的直径)，并更新最大直径。
/**
* 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 {
// 定义一个变量res，用来保存最大直径
int res;
public int diameterOfBinaryTree(TreeNode root) {
// 初始化最大直径为0(因为节点个数可以是1个，所以最大直径可以是0)
res = 0;
// 调用递归函数，计算以根节点为根的树的直径
findDeepth(root);
return res;
}
public int findDeepth(TreeNode treeNode){
if(treeNode == null){
return 0;
}
int left = findDeepth(treeNode.left);
int right = findDeepth(treeNode.right);
// 更新最大直径
res = Math.max(res,left + right);
return Math.max(left,right)+1;
}
}