树与二叉树

二叉树基础

定义

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

遍历方式

前序遍历（根-左-右）

void preorder(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);  // 访问根
    preorder(root.left);           // 遍历左子树
    preorder(root.right);          // 遍历右子树
}

中序遍历（左-根-右）

void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.println(root.val);
    inorder(root.right);
}

后序遍历（左-右-根）

void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.println(root.val);
}

层序遍历（BFS）

void levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val);
        
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

二叉搜索树（BST）

性质

• 左子树所有节点 < 根节点
• 右子树所有节点 > 根节点
• 左右子树也是BST

查找 - O(log n) ~ O(n)

TreeNode search(TreeNode root, int target) {
    if (root == null || root.val == target) return root;
    if (target < root.val) return search(root.left, target);
    return search(root.right, target);
}

经典题目

• 二叉树的最大深度
• 判断平衡二叉树
• 二叉树的最近公共祖先
• 序列化与反序列化二叉树