Java怎么根据前序后序构建二叉树

共计 1168 个字符，预计需要花费 3 分钟才能阅读完成。

在 Java 中，可以根据给定的前序遍历和后序遍历数组构建二叉树。下面是一个示例代码：

class TreeNode {int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {this.val = val;
    }
}

public class BinaryTreeBuilder {public TreeNode buildTree(int[] preOrder, int[] postOrder) {return buildTreeHelper(preOrder, postOrder, 0, preOrder.length - 1, 0, postOrder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] preOrder, int[] postOrder, int preStart, int preEnd, int postStart, int postEnd) {if (preStart > preEnd || postStart > postEnd) {return null;
        }

        TreeNode root = new TreeNode(preOrder[preStart]);

        if (preStart == preEnd) {return root;
        }

        int leftRootVal = preOrder[preStart + 1];
        int leftRootIndex = postStart;
        while (postOrder[leftRootIndex] != leftRootVal) {leftRootIndex++;}

        int leftTreeSize = leftRootIndex - postStart + 1;

        root.left = buildTreeHelper(preOrder, postOrder, preStart + 1, preStart + leftTreeSize, postStart, leftRootIndex);
        root.right = buildTreeHelper(preOrder, postOrder, preStart + leftTreeSize + 1, preEnd, leftRootIndex + 1, postEnd - 1);

        return root;
    }
}

在这段代码中，我们首先定义了一个 TreeNode 类表示二叉树的节点。然后定义了一个 BinaryTreeBuilder 类来构建二叉树。在 buildTree 方法中，我们调用 buildTreeHelper 方法来递归构建二叉树。在 buildTreeHelper 方法中，我们首先创建根节点，并根据前序遍历数组和后序遍历数组的特点，找到左子树的根节点值和左子树的大小，然后递归构建左子树和右子树。

最后，我们可以调用 buildTree 方法来构建二叉树，并传入前序遍历数组和后序遍历数组作为参数。

丸趣 TV 网 – 提供最优质的资源集合！