跳到主要内容

二叉树

问题​

二叉树的遍历方式有哪些？常见的二叉树面试题？

答案​

树节点定义​

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

遍历方式​

方式顺序应用
前序遍历根→左→右复制树
中序遍历左→根→右BST 有序输出
后序遍历左→右→根删除树、计算高度
层序遍历逐层从左到右BFS

递归遍历​

前序 / 中序 / 后序
// 前序
public void preorder(TreeNode root) {
    if (root == null) return;
    visit(root);              // 先访问根
    preorder(root.left);
    preorder(root.right);
}

// 中序
public void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    visit(root);              // 中间访问根
    inorder(root.right);
}

层序遍历（BFS）​

层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

最大深度​

递归求最大深度
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

验证二叉搜索树（BST）​

BST 验证：中序遍历有序
private long prev = Long.MIN_VALUE;

public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    // 中序遍历：左子树 → 根 → 右子树，应严格递增
    if (!isValidBST(root.left)) return false;
    if (root.val <= prev) return false;
    prev = root.val;
    return isValidBST(root.right);
}

最近公共祖先（LCA）​

最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;  // p 和 q 分布在两侧
    return left != null ? left : right;
}

常见面试问题​

Q1: 如何判断一棵二叉树是否对称？​

答案：

public boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

private boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return t1.val == t2.val
        && isMirror(t1.left, t2.right)
        && isMirror(t1.right, t2.left);
}

Q2: 二叉树和 Java 中的哪些数据结构相关？​

答案：

数据结构底层
TreeMap / TreeSet红黑树（自平衡 BST）
PriorityQueue堆（完全二叉树）
HashMap（JDK 8+）链表长度 > 8 转红黑树

相关链接​