跳到主要内容数据结构：二叉树经典习题讲解 | 极客日志Javajava算法
数据结构：二叉树经典习题讲解
本文讲解了二叉树的多种经典算法问题，包括判断两树是否相等、翻转、平衡性检查、对称性判断、由遍历序列构建、层序遍历及最近公共祖先。同时涵盖了前序、后序遍历的递归与迭代实现。代码基于 Java 语言，重点阐述了递归终止条件、返回值处理及栈在迭代中的应用。
CodeArtist2 浏览 递归重要注意事项：
- 递归掌握的关键在于想清楚第一层非递归逻辑以及递归结束条件（最后一层）。结束条件有时有多个，尽量合并。
- 有返回值的递归：
- 大概率需要接收下一层递归的返回值，整理后继续向上返回。
- 若返回值需叠加（如求高度），必须接收。
1.1. 判断两个二叉树是否相等
题目链接
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q != null || p != null && q == null) {
return false;
}
if (p == null && q == null) {
return true;
}
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
1.2. 相同的二叉树与子树
相同的树
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q != null || p != null && q == null) {
return false;
}
if (p == null && q == null) {
return true;
}
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
public {
(isSameTree(root, subRoot)) {
;
}
(root == ) {
;
}
isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
- Escape 与 Native 编解码
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
- JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
- JavaScript 压缩与混淆
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
boolean
isSubtree
(TreeNode root, TreeNode subRoot)
if
return
true
if
null
return
false
return
1.3. 翻转二叉树
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
1.4. 平衡二叉树
int getHeight2(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight2(root.left);
int rightHeight = getHeight2(root.right);
if (Math.abs(leftHeight - rightHeight) <= 1 && leftHeight >= 0 && rightHeight >= 0) {
return Math.max(leftHeight, rightHeight) + 1;
}
return -1;
}
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return getHeight2(root) >= 0;
}
1.5. 对称二叉树
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSample(root.left, root.right);
}
public boolean isSample(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
return isSample(p.left, q.right) && isSample(p.right, q.left);
}
1.6. 通过字符串构建二叉树
import java.util.Scanner;
class TreeNode {
char val;
TreeNode left;
TreeNode right;
public TreeNode() {}
public TreeNode(char val) { this.val = val; }
}
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String str = in.nextLine();
TreeNode root = create(str);
inorder(root);
}
}
public static int i = 0;
public static TreeNode create(String str) {
if (str.charAt(i) == '#') {
i++;
return null;
} else {
TreeNode root = new TreeNode(str.charAt(i));
i++;
root.left = create(str);
root.right = create(str);
return root;
}
}
public static void inorder(TreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
}
1.7. 二叉树分层遍历
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if (root == null) {
return list;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
int size = queue.size();
while (size != 0) {
TreeNode cur = queue.poll();
tmp.add(cur.val);
size--;
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
list.add(tmp);
}
return list;
}
1.8. 二叉树的最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p == root || q == root) {
return root;
}
if (root == null) {
return null;
}
TreeNode leftRoot = lowestCommonAncestor(root.left, p, q);
TreeNode rightRoot = lowestCommonAncestor(root.right, p, q);
if (leftRoot != null && rightRoot != null) {
return root;
} else if (leftRoot != null) {
return leftRoot;
} else {
return rightRoot;
}
}
private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
if (root == null || node == null) {
return false;
}
stack.push(root);
if (root == node) {
return true;
}
boolean flg1 = getPath(root.left, node, stack);
if (flg1) {
return true;
}
boolean flg2 = getPath(root.right, node, stack);
if (flg2) {
return true;
}
stack.pop();
return false;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
getPath(root, p, stack1);
getPath(root, q, stack2);
int size = stack1.size() - stack2.size();
if (size > 0) {
while (size != 0) {
stack1.pop();
size--;
}
} else {
while (size != 0) {
stack2.pop();
size++;
}
}
while (!stack1.isEmpty() && !stack2.isEmpty()) {
if (stack1.peek().equals(stack2.peek())) {
return stack1.peek();
}
stack1.pop();
stack2.pop();
}
return null;
}
1.9. 从前序与中序遍历序列构造二叉树
class Solution {
public int preIndex;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
}
private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend) {
if (inbegin > inend) {
return null;
}
if (inbegin == inend) {
int pre = preIndex;
preIndex++;
return new TreeNode(preorder[pre]);
}
int rootIndex = findIndex(inorder, inbegin, inend, preorder[preIndex]);
if (rootIndex == -1) {
return null;
}
TreeNode root = new TreeNode(preorder[preIndex]);
preIndex++;
root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex - 1);
root.right = buildTreeChild(preorder, inorder, rootIndex + 1, inend);
return root;
}
private int findIndex(int[] inorder, int inbegin, int inend, int key) {
for (int i = inbegin; i <= inend; i++) {
if (inorder[i] == key) {
return i;
}
}
return -1;
}
}
1.10. 从中序与后序遍历序列构造二叉树
class Solution {
public int postIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postIndex = postorder.length - 1;
return buildTreeChild(postorder, inorder, 0, inorder.length - 1);
}
private TreeNode buildTreeChild(int[] postorder, int[] inorder, int inbegin, int inend) {
if (inbegin > inend) {
return null;
}
int rootIndex = findIndex(inorder, inbegin, inend, postorder[postIndex]);
if (rootIndex == -1) {
return null;
}
TreeNode root = new TreeNode(postorder[postIndex]);
postIndex--;
root.right = buildTreeChild(postorder, inorder, rootIndex + 1, inend);
root.left = buildTreeChild(postorder, inorder, inbegin, rootIndex - 1);
return root;
}
private int findIndex(int[] inorder, int inbegin, int inend, int key) {
for (int i = inbegin; i <= inend; i++) {
if (inorder[i] == key) {
return i;
}
}
return -1;
}
}
1.11. 前序遍历二叉树（迭代实现）
public static void preOrder1(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
System.out.print(cur.val);
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
cur = cur.right;
}
}
1.12. 后序遍历二叉树（迭代实现）
public static void postOrder1(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode prev = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
if (top.right == null || top.right == prev) {
stack.pop();
System.out.print(top.val + " ");
prev = top;
} else {
cur = top.right;
}
}
}
