leetcode106 根据中序遍历和后序遍历如何还原二叉树?

发布于 2022-09-03 12:04:56 字数 1538 浏览 19 评论 0

public class ConstructBinaryTreeFromInorderAndPostorderTraversal
{
    int pInorder;   // index of inorder array
    int pPostorder; // index of postorder array

    private TreeNode buildTree(int[] inorder, int[] postorder, TreeNode end) {
        if (pPostorder < 0) {
            return null;
        }

        // create root node
        TreeNode n = new TreeNode(postorder[pPostorder--]);

        // if right node exist, create right subtree
        if (inorder[pInorder] != n.val) {
            n.right = buildTree(inorder, postorder, n);
        }

        pInorder--;

        // if left node exist, create left subtree
        if ((end == null) || (inorder[pInorder] != end.val)) {
            n.left = buildTree(inorder, postorder, end);
        }

        return n;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        pInorder = inorder.length - 1;
        pPostorder = postorder.length - 1;

        return buildTree(inorder, postorder, null);
    }

    public static void main(String[] args) {
        int[] a = new int[]{
                1,2,3,4,5,6,7
        } ;
        int[] b = new int[]{
                1,3,2,5,7,6,4
        } ;

        TreeNode t = new ConstructBinaryTreeFromInorderAndPostorderTraversal().buildTree(a , b) ;
        System.out.println(t);
    }
}

这个是leetcode地址: https://leetcode.com/problems...

该如何理解这个算法?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文