Java recursive solution, O(n)


  • 0
    J

    slower than iterative solution, but easier to understand.

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if (inorder.length == 0) return null;
            return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
        }
        
        private TreeNode buildTree(int[] inorder, int s1, int e1, int[] postorder, int s2, int e2) {
            if (s2 > e2) return null;
            TreeNode root = new TreeNode(postorder[e2]);
            if (s2 == e2) return root;
            int rootIdx = -1;
            for (int i = s1; i <= e1; i++) {
                if (inorder[i] == root.val) {
                    rootIdx = i;
                    break;
                }
            }
            root.left = buildTree(inorder, s1, rootIdx - 1, postorder, s2, s2 + rootIdx - 1 - s1);
            root.right = buildTree(inorder, rootIdx + 1, e1, postorder, s2 + rootIdx - s1, e2 - 1);
            return root;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.