二叉树遍历与递归思想

一、二叉树基础

1.1 节点定义

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

1.2 二叉树类型

类型	特性
满二叉树	每个节点都有0或2个子节点
完全二叉树	除最后一层外全满，最后一层左连续
二叉搜索树	左 < 根 < 右
平衡二叉树	任意节点左右高度差 ≤ 1

1.3 基本性质

• 第 ( i ) 层最多 ( 2^{i-1} ) 个节点
• 深度为 ( k ) 的树最多 ( 2^k - 1 ) 个节点
• 叶子节点数 = 度为2的节点数 + 1

二、递归思想

2.1 递归三要素

1. 终止条件：何时停止递归
2. 递归函数：递归要做什么
3. 递归公式：如何缩小问题规模

2.2 树问题的递归框架

void traverse(TreeNode root) {
    if (root == null) return;  // 终止条件
    
    // 前序位置：访问root
    traverse(root.left);       // 递归左子树
    // 中序位置
    traverse(root.right);      // 递归右子树
    // 后序位置
}

三、深度优先遍历(DFS)

3.1 前序遍历（根-左-右）

// 递归
public List<Integer> preorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    helper(root, res);
    return res;
}

void helper(TreeNode node, List<Integer> res) {
    if (node == null) return;
    res.add(node.val);           // 访问根
    helper(node.left, res);      // 遍历左
    helper(node.right, res);     // 遍历右
}

// 迭代 - 使用栈
public List<Integer> preorderIterative(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return res;
}

3.2 中序遍历（左-根-右）

// 递归
void inorder(TreeNode node, List<Integer> res) {
    if (node == null) return;
    inorder(node.left, res);
    res.add(node.val);
    inorder(node.right, res);
}

// 迭代
public List<Integer> inorderIterative(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        res.add(curr.val);
        curr = curr.right;
    }
    return res;
}

3.3 后序遍历（左-右-根）

// 递归
void postorder(TreeNode node, List<Integer> res) {
    if (node == null) return;
    postorder(node.left, res);
    postorder(node.right, res);
    res.add(node.val);
}

// 迭代（双栈法）
public List<Integer> postorderIterative(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack1 = new ArrayDeque<>();
    Deque<TreeNode> stack2 = new ArrayDeque<>();
    if (root != null) stack1.push(root);
    
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        if (node.left != null) stack1.push(node.left);
        if (node.right != null) stack1.push(node.right);
    }
    while (!stack2.isEmpty()) {
        res.add(stack2.pop().val);
    }
    return res;
}

四、广度优先遍历(BFS)

4.1 层序遍历

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    
    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);
        }
        res.add(level);
    }
    return res;
}

五、Morris遍历（常数空间）

5.1 核心思想

利用叶子节点的空指针，建立临时线索，实现 ( O(1) ) 空间遍历。

5.2 Morris中序遍历

public List<Integer> morrisInorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    TreeNode curr = root;
    
    while (curr != null) {
        if (curr.left == null) {
            res.add(curr.val);
            curr = curr.right;
        } else {
            TreeNode predecessor = curr.left;
            while (predecessor.right != null && predecessor.right != curr) {
                predecessor = predecessor.right;
            }
            
            if (predecessor.right == null) {
                predecessor.right = curr;  // 建立线索
                curr = curr.left;
            } else {
                predecessor.right = null;  // 删除线索
                res.add(curr.val);
                curr = curr.right;
            }
        }
    }
    return res;
}

六、遍历的应用

6.1 中序遍历恢复BST

TreeNode prev = null;
TreeNode first = null, second = null;

void recoverBST(TreeNode root) {
    inorder(root);
    swap(first, second);
}

void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    if (prev != null && prev.val > root.val) {
        if (first == null) first = prev;
        second = root;
    }
    prev = root;
    inorder(root.right);
}

6.2 树的序列化与反序列化

// 前序序列化
String serialize(TreeNode root) {
    if (root == null) return "#,";
    return root.val + "," + serialize(root.left) + serialize(root.right);
}

TreeNode deserialize(String data) {
    String[] nodes = data.split(",");
    Queue<String> queue = new LinkedList<>(Arrays.asList(nodes));
    return build(queue);
}

TreeNode build(Queue<String> queue) {
    String val = queue.poll();
    if ("#".equals(val)) return null;
    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left = build(queue);
    node.right = build(queue);
    return node;
}

七、总结

遍历方式	顺序	典型应用
前序	根-左-右	复制树、序列化
中序	左-根-右	BST排序、恢复树
后序	左-右-根	计算高度、路径和
层序	按层	最短路径、连接节点

递归是树问题的天然解法，理解递归框架的「前序/中序/后序位置」概念，能系统解决大部分树问题。