ac solution code


  • 0
        /*
         Solution1. time = lgn(Division) * lgn(Search in in-order array) = O(n); space = O(1)
         Same as pre-order, just take the root from the end of post-order array.
         
         post-order array A: left right root
         in-order  array  B: left root right
         
         1) Find `root`: Take the last one of post-order as root
         2) Search `root` in in-order array at i:
         Divide A into left and right parts: "0..i-1, i+1..n-1"
         Divide B into left and right parts: "0..i-1, i+1..n-1"
         3) Keep the recursion with the above steps.
         */
        func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
            return buildTree(postorder, 0, postorder.count - 1, inorder, 0, inorder.count - 1)
        }
        
        func buildTree(_ postorder: [Int], _ postStart: Int, _ postEnd: Int, _ inorder: [Int], _ inStart: Int, _ inEnd: Int) -> TreeNode? {
            guard inStart <= inEnd else {return nil} //<--
            let root = TreeNode(postorder[postEnd]) // Take postorder.last as  root
            let pos = findPos(postorder[postEnd], inorder, inStart, inEnd) // Find root index in inorder array
            
            if pos != -1 {
                if pos - 1 >= 0 {// build left branch <--postStart+pos-inStart-1
                    root.left = buildTree(postorder, postStart, postStart + pos - inStart - 1, inorder, inStart, pos - 1)
                }
                if pos + 1 <= inEnd {// build right branch <--
                    root.right = buildTree(postorder, postStart + pos - inStart, postEnd - 1, inorder, pos + 1, inEnd)
                }
            }
            return root
        }
        
        /// Find position of key in inorder array with start/end bounds
        func findPos(_ key: Int, _ inorder: [Int], _ inStart: Int, _ inEnd: Int) -> Int {
            for i in inStart...inEnd where inorder[i] == key {
                return i
            }
            return -1
        }
    

Log in to reply
 

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