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

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

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...

该如何理解这个算法?

【热门文章】
【热门文章】