10-- construct binary tree according to middle order traversal and post order traversal

Github link

The idea is as follows

 // Middle preface :   [4, 1,  5,  3, 6, 2, 7] --> Record in the dictionary : [[4: 0], [1: 1], [5: 2],[3: 3],[6: 4],[2: 5],[7: 6]]

 //  In the following order :  [4, 5, 1, 6,   7,   2, 3]

  For the subsequent array , From back to front

 0. curIndex = 6

 1. When taking 3 When , index =>  dict[3] = 3 , hold curIndex = 5

 2. Then the successor nodes of the current root node , by index + 1 = 4

   The predecessor node of the current root node , by index - 1 = 2

 3. First find the right side of the current root node , Find the left side again , Recursively call

 4. When left > right Do not conform to the

 5. The second step , When recursion comes in , The left of the parameter is 4, The right side of the parameter is 6

 rootVal = 2

 rootNode = TreeNode(rootVal)

  The new root node is 2, From the dictionary index --> dict[2] = 5, hold curIndex = 4

  The right value : TreeNode(7)  left = (index + 1) == 6, right =  6

  Left value : TreeNode(6) left = 4, right = (curIndex - 1) == 4

Methods to summarize

 1. Middle order traversal is used to generate dictionaries

 2. After the sequence traversal , From back to front , Generate right , The left node , Recursively call

/**
 //  Middle preface :  Left -  root  -  Right 
 //  In the following order :  Left -  Right  -  root 
  give an example :
 ----------------------------------
          3
    1                       2
 4            5          6              7
 //  Middle preface :   [4, 1,  5,  3, 6, 2, 7] -->  Record in the dictionary : [[4: 0], [1: 1], [5: 2],[3: 3],[6: 4],[2: 5],[7: 6]]
 //   In the following order :  [4, 5, 1, 6,   7,   2, 3]
 
  For the subsequent array , From back to front 
 0. curIndex = 6
 1.  When taking 3 When , index =>  dict[3] = 3 ,  hold curIndex = 5
 2. Then the successor nodes of the current root node ,  by index + 1 = 4
    The predecessor node of the current root node ,  by index - 1 = 2
 3.  First find the right side of the current root node  ,  Find the left side again , Recursively call 
 4.  When left > right  Do not conform to the 
 
 5.  The second step , When recursion comes in , The left of the parameter is 4, The right side of the parameter is 6
 rootVal = 2
 rootNode = TreeNode(rootVal)
  The new root node is  2,  From the dictionary index --> dict[2] = 5,  hold curIndex = 4
  The right value : TreeNode(7)  left = (index + 1) == 6, right =  6
  Left value : TreeNode(6) left = 4, right = (curIndex - 1) == 4
 
 ------------------
  summary :
 1.  Middle order traversal is used to generate dictionaries 
 2.  After the sequence traversal , From back to front , Generate right , The left node , Recursively call 
 */
class xiapi10 {
    var myPostorder = [Int]()
    var curIndex = 0
    var dict = [Int: Int]()
    
    func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode10? {
        myPostorder = postorder
        curIndex = myPostorder.count - 1
        
        for index in 0..<inorder.count {
            dict[inorder[index]] = index
        }
        
        return getNodeByLeftAndRight(0, myPostorder.count - 1)
        
    }
    
    func getNodeByLeftAndRight(_ left: Int, _ right: Int) -> TreeNode10? {
        if left > right {
            return nil
        }
        
        let rootVal = myPostorder[curIndex]
        let rootNode = TreeNode10(rootVal)
        
        guard let index = dict[rootVal] else {
            return nil
        }
        curIndex -= 1
        rootNode.right = getNodeByLeftAndRight(index + 1, right)
        rootNode.left = getNodeByLeftAndRight(left, index - 1)
        
        return rootNode
    }
    
}

class TreeNode10 {
    var val: Int
    var left: TreeNode10?
    var right: TreeNode10?
    
    init() {
        self.val = 0
        self.left = nil
        self.right = nil
    }
    
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
    
    init(_ val: Int, _ left: TreeNode10?, _ right: TreeNode10?) {
        self.val = 0
        self.left = left
        self.right = right
    }
    
}