LC-二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树、二叉树的直径

二叉树的中序遍历

递归

时间复杂度： O(N) （每个节点访问一次）
空间复杂度： O(N) （最坏情况下递归栈深度为 O(N)）

/*** 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 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){return;}inorder(node.left,result);//递归左子树result.add(node.val);//访问根节点inorder(node.right,result);//递归右子树}
}

迭代

时间复杂度： O(N)
空间复杂度： O(N) （最坏情况下栈深度为 O(N)）

/*** 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 List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while(cur != null || !stack.isEmpty()){while(cur != null){//访问左子树stack.push(cur);cur = cur.left;}cur = stack.pop();//访问根节点result.add(cur.val);cur = cur.right;//访问右子树}return result;}
}

二叉树的最大深度

递归（DFS - 深度优先搜索）

/*** 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;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return Math.max(leftDepth,rightDepth) + 1;}
}

迭代（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 int maxDepth(TreeNode root) {if(root == null){return 0;}// 初始化队列，并加入根节点Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int depth = 0;while(!queue.isEmpty()){int size = queue.size(); // 当前层的节点数depth++; // 每遍历一层，深度 +1for(int i = 0;i < size;i++){TreeNode node = queue.poll();// 取出当前层的节点// 将左右子节点加入队列if(node.left != null){queue.offer(node.left);}if(node.right != null){queue.offer(node.right);}}}return depth;}
}

翻转二叉树

递归（DFS 深度优先搜索）

递归终止条件：如果 root == null，直接返回 null。
交换左右子树：
- 递归调用 invertTree(root.left) 和 invertTree(root.right) 交换左右子节点。
- 交换后的左子树赋值给 root.right，右子树赋值给 root.left。
返回当前节点，保证整个二叉树翻转完成。

时间复杂度：O(N)，每个节点访问一次。

空间复杂度：O(H)，递归调用栈的最大深度（H 为二叉树高度，最坏 O(N)）。

/*** 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.left = right;root.right = left;return root;}
}

迭代（BFS 广度优先搜索）

使用队列 (Queue<TreeNode>) 进行 层序遍历。
遍历每个节点，交换其左右子树。
依次将子节点加入队列，保证所有节点都能被访问并交换。

时间复杂度：O(N)，每个节点访问一次。

空间复杂度：O(N)，队列最多存储 N/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 {public TreeNode invertTree(TreeNode root) {if(root == null){return null;}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;}
}

对称二叉树

递归（DFS）

如果二叉树是对称的，那么它的 左子树 和 右子树 必须是镜像的。
递归检查左右子树：
1. p.left.val == q.right.val 且 p.right.val == q.left.val
2. p.left 的左子树与 q.right 的右子树对称
3. p.right 的右子树与 q.left 的左子树对称

/*** 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) {if(root == null){return true;}return isMirror(root.left,root.right);}//判断两个子树是否互为镜像private boolean isMirror(TreeNode p,TreeNode q){if(p == null && q == null){return true;}if(p == null || q == null){return false;}return (p.val == q.val) && isMirror(p.left,q.right) && isMirror(p.right,q.left);}
}

迭代（BFS 层序遍历）

使用队列 (Queue<TreeNode>) 进行层序遍历。
每次同时取出 两个节点：
- 检查它们是否对称（值相等）
- 交换顺序 继续入队：
  - p.left 和 q.right
  - p.right 和 q.left

/*** 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) {if(root == null){return true;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root.left);queue.offer(root.right);while(!queue.isEmpty()){TreeNode p = queue.poll();TreeNode q = queue.poll();if(p == null && q == null){continue;}if(p == null || q == null || p.val != q.val){return false;}//交换顺序加入队列queue.offer(p.left);queue.offer(q.right);queue.offer(p.right);queue.offer(q.left);}return true;}
}

二叉树的直径

递归（DFS）

递归计算每个节点的深度（即 以该节点为根的子树的最大深度）。
计算当前节点的直径：
- 直径 = 左子树深度 + 右子树深度。
- 更新全局最大直径 maxDiameter。
返回当前节点的深度：
- 当前节点的深度 = max(左子树深度, 右子树深度) + 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 {private int maxDiameter = 0;public int diameterOfBinaryTree(TreeNode root) {depth(root);return maxDiameter;}private int depth(TreeNode node){if(node == null){return 0;}//递归计算左右子树的深度int leftDepth = depth(node.left);int rightDepth = depth(node.right);//计算当前节点的直径并更新最大值maxDiameter = Math.max(maxDiameter,leftDepth + rightDepth);//返回当前节点的深度return Math.max(leftDepth,rightDepth) + 1;}
}