21 - vertical traversal of binary tree

1. subject

GitHub Brush the algorithm together

• Title Description
  

• Ideas

/**
Ideas :

1. From the top down BFS
2. From left to right DFS
   */

/**
Code explanation :
0. Define a dictionary , Store the results of each column [key: Value] = [Int: [Int]]

1. Define a queue , Deposit node
2. Define a queue , Storage location , On the left -1, On the right +1
3. Take out the queue every time , Update dictionary's key - Value
4. Traversing the dictionary value, Traverse from left to right , Put in res
   */

• Code

    func verticalOrder(_ root: TreeNode?) -> [[Int]] {
        var res = [[Int]]()
        if root == nil { return res }
        
        var dict: [Int: [Int]] = [Int: [Int]]()
        
        var queueValue = [TreeNode]()
        if let root = root {
            queueValue.append(root)
        }
        
        var queuePosition = [Int]()
        queuePosition.append(0)
        
        var leftPos = Int.max
        
        while !queueValue.isEmpty {
            let node = queueValue.removeFirst()
            let pos = queuePosition.removeFirst()
            
            var subArr = dict[pos, default: [Int]()]
            subArr.append(node.val)
            dict[pos] = subArr
            
            if node.left != nil {
                queueValue.append(node.left!)
                queuePosition.append(pos - 1)
            }
            
            if node.right != nil {
                queueValue.append(node.right!)
                queuePosition.append(pos + 1)
            }
            
            leftPos = min(leftPos, pos)
        }
        
        for i in leftPos..<leftPos + dict.count {
            if let subArr = dict[i] {
                res.append(subArr)
            }
        }
        
        return res
    }

• Submit results