Java LeetCode篇-深入了解二叉树的经典解法（多种方式实现：构造二叉树）

在 LeetCode 上，二叉树是一种常见的数据结构，构造二叉树的方法变化多样，掌握其经典解法对于解决各种二叉树相关的问题非常重要。本文将深入探讨几种常用的构造二叉树的方式，并提供相应的 Java 代码示例。

一、前序遍历与中序遍历构造二叉树

最常用的构造二叉树的方法是根据前序遍历和中序遍历的结果。我们可以利用前序遍历的第一个节点作为树的根节点，然后在中序遍历中找到该根节点的位置，进而确定其左子树和右子树的范围。

以下是具体的实现代码：

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

public class Solution {
    private int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;

        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);

        int inIndex = 0; // 找到根节点在中序遍历中的索引
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                inIndex = i;
                break;
            }
        }

        // 递归构造左子树和右子树
        root.left = buildTree(preorder, inorder, inStart, inIndex - 1);
        root.right = buildTree(preorder, inorder, inIndex + 1, inEnd);

        return root;
    }
}

二、后序遍历与中序遍历构造二叉树

同样的逻辑也适用于后序遍历和中序遍历。后序遍历的最后一个节点是树的根节点。在中序遍历中找到根节点，再确定左右子树的范围。

代码实现如下：

public class Solution {
    private int postIndex;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        return buildTree(inorder, postorder, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] inorder, int[] postorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;

        int rootVal = postorder[postIndex--];
        TreeNode root = new TreeNode(rootVal);

        // 找到根节点在中序遍历中的索引
        int inIndex = 0; 
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                inIndex = i;
                break;
            }
        }

        // 递归构造右子树和左子树
        root.right = buildTree(inorder, postorder, inIndex + 1, inEnd);
        root.left = buildTree(inorder, postorder, inStart, inIndex - 1);

        return root;
    }
}

三、层序遍历构造完全二叉树

如果我们有一个层序遍历的数组，可以直接构造一个完全二叉树。按照层序遍历的顺序，我们可以通过队列来逐层构造树。

以下是使用 Java 实现的代码示例：

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public TreeNode buildTree(int[] levelOrder) {
        if (levelOrder == null || levelOrder.length == 0) return null;

        TreeNode root = new TreeNode(levelOrder[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();

            // 构造左子树
            if (i < levelOrder.length) {
                current.left = new TreeNode(levelOrder[i++]);
                queue.offer(current.left);
            }

            // 构造右子树
            if (i < levelOrder.length) {
                current.right = new TreeNode(levelOrder[i++]);
                queue.offer(current.right);
            }
        }

        return root;
    }
}

结论

以上三种方法是构造二叉树的经典解法，每种方法都有其应用场景和适用条件。在实际编程面试和算法竞赛中，熟练掌握这些方法能够帮助我们快速解决与二叉树相关的问题。希望通过本文的讲解，能够对读者理解和实现二叉树的构造有一定的帮助。