Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

解法：

根据后序和中序遍历还原二叉树，解法与 Leetcode(105) Construct Binary Tree from Preorder and Inorder Traversal类似。代码如下：

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

    private TreeNode mybuild(int[] inorder, int startin, int endin, int[] postorder, int startpost, int endpost) {
        if (startin > endin || startpost > endpost) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[endpost]);
        for (int i = startin; i <= endin; i++) {
            if (inorder[i] == root.val) {
                root.left = mybuild(inorder, startin, i - 1, postorder, startpost, startpost + i - startin - 1);
                root.right = mybuild(inorder, i + 1, endin, postorder, startpost + i - startin, endpost - 1);
            }
        }
        return root;
    }
}

leetcode(106) construct binary tree from inorder and postorder traversal 解法：

解法：

近期文章

近期评论

标签

热门

文章归档

分类目录

功能