跳到主要内容

树与二叉树基础

树是一种非线性的层次数据结构，广泛应用于文件系统、数据库索引、编译器等场景。

树的基本概念​

定义​

树是由 n（n ≥ 0）个节点组成的有限集合：

  • n = 0 时，称为空树
  • n > 0 时，有一个特殊的节点称为根节点
  • 其余节点分为 m（m > 0）个互不相交的有限集合，每个集合又是一棵树

基本术语​

术语定义
节点树中的基本单元
根节点没有父节点的节点
叶子节点没有子节点的节点
内部节点有子节点的非根节点
父节点直接上级节点
子节点直接下级节点
兄弟节点具有相同父节点的节点
节点的度子节点的个数
树的度所有节点度的最大值
节点的层次从根到该节点的路径长度（根节点为第 1 层）
树的高度节点的最大层次
深度从根到该节点的边数

二叉树​

二叉树是每个节点最多有两个子节点的树。

二叉树的性质​

  1. 第 i 层最多有 2^(i-1) 个节点
  2. 深度为 k 的二叉树最多有 2^k - 1 个节点
  3. 对于任意二叉树，叶子节点数 = 度为 2 的节点数 + 1

二叉树的实现​

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

二叉树的遍历​

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

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

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

// 迭代
public List<Integer> preorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        
        // 先右后左，保证左子树先遍历
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    
    return result;
}

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

// 递归
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);   // 遍历右子树
}

// 迭代
public List<Integer> inorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // 先遍历到最左边的节点
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        // 访问节点
        current = stack.pop();
        result.add(current.val);
        
        // 转向右子树
        current = current.right;
    }
    
    return result;
}

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

// 递归
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorder(root, result);
    return result;
}

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

// 迭代（使用前序遍历的逆序）
public List<Integer> postorderTraversalIterative(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    if (root == null) return result;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.addFirst(node.val);  // 头插法
        
        // 先左后右
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    
    return result;
}

层序遍历​

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 levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < levelSize; 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;
}

特殊二叉树​

特殊二叉树​

满二叉树​

所有叶子节点都在同一层，且每个内部节点都有两个子节点。

        1
       / \
      2   3
     / \ / \
    4  5 6  7

完全二叉树​

除了最后一层，其他层都是满的，最后一层从左到右排列。

        1
       / \
      2   3
     / \ /
    4  5 6

完全二叉树的数组表示：

对于索引 i（从 0 开始）：

  • 父节点索引：(i - 1) / 2
  • 左子节点索引：2 * i + 1
  • 右子节点索引：2 * i + 2
public class ArrayBinaryTree {
    private int[] data;
    
    public ArrayBinaryTree(int[] data) {
        this.data = data;
    }
    
    public int parent(int i) {
        return (i - 1) / 2;
    }
    
    public int leftChild(int i) {
        return 2 * i + 1;
    }
    
    public int rightChild(int i) {
        return 2 * i + 2;
    }
}

二叉搜索树 (BST) 与 平衡二叉树 (AVL)​

详见 二叉搜索树 章节。

经典二叉树问题​

1. 二叉树的最大深度​

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

2. 翻转二叉树​

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

3. 对称二叉树​

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

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

4. 二叉树的最近公共祖先​

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;
}

5. 从前序与中序遍历构造二叉树​

public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    
    return build(preorder, 0, preorder.length - 1, 
                 inorder, 0, inorder.length - 1, inorderMap);
}

private TreeNode build(int[] preorder, int preStart, int preEnd,
                       int[] inorder, int inStart, int inEnd,
                       Map<Integer, Integer> inorderMap) {
    if (preStart > preEnd || inStart > inEnd) {
        return null;
    }
    
    int rootVal = preorder[preStart];
    TreeNode root = new TreeNode(rootVal);
    
    int inRoot = inorderMap.get(rootVal);
    int leftSize = inRoot - inStart;
    
    root.left = build(preorder, preStart + 1, preStart + leftSize,
                      inorder, inStart, inRoot - 1, inorderMap);
    root.right = build(preorder, preStart + leftSize + 1, preEnd,
                       inorder, inRoot + 1, inEnd, inorderMap);
    
    return root;
}

小结​

本章我们学习了：

  1. 树的基本概念：节点、根、叶子、层次、高度等
  2. 二叉树遍历：前序、中序、后序、层序
  3. 特殊二叉树：满二叉树、完全二叉树、BST、AVL 树
  4. 经典问题：最大深度、翻转、对称、LCA、构造二叉树

练习​

  1. LeetCode 104：二叉树的最大深度
  2. LeetCode 226：翻转二叉树
  3. LeetCode 101：对称二叉树
  4. LeetCode 236：二叉树的最近公共祖先
  5. LeetCode 105：从前序与中序遍历序列构造二叉树
  6. LeetCode 98：验证二叉搜索树