二叉树递归算法创建二叉树

二叉树是一种常见的数据结构，在递归算法中也有很多应用。创建二叉树的递归算法可以分为前序遍历和中序遍历两种方式。

前序遍历方式下，我们按照“根-左-右”的顺序来构建二叉树。具体步骤如下：
1. 如果输入的节点值为null，则返回空节点。
2. 创建一个新的节点，将其值设置为当前的节点值。
3. 递归调用函数，将左子树的根节点设置为当前节点的左子节点。
4. 递归调用函数，将右子树的根节点设置为当前节点的右子节点。
5. 返回当前节点。

中序遍历方式下，我们按照“左-根-右”的顺序来构建二叉树。具体步骤如下：
1. 如果输入的节点值为null，则返回空节点。
2. 递归调用函数，将左子树的根节点设置为当前节点的左子节点。
3. 创建一个新的节点，将其值设置为当前的节点值。
4. 递归调用函数，将右子树的根节点设置为当前节点的右子节点。
5. 返回当前节点。

下面是一个示例代码，以前序遍历方式为例：

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

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

    private TreeNode build(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        int rootVal = preorder[preStart];
        int index = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }

        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, inorder, preStart + 1, preStart + index - inStart, inStart, index - 1);
        root.right = build(preorder, inorder, preStart + index - inStart + 1, preEnd, index + 1, inEnd);

        return root;
    }
}