Leetcode - vertical-order-traversal-of-a-binary-tree

violet posted @ Mar 14, 2020 05:45:37 AM in 算法 with tags Algorithm tree BFS Golang , 352 阅读

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Use bfs to traverse the tree, store a hash: hd -> tree value

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type TreeWithDistance struct {
    node  *TreeNode
    hd    int
    level int
}

func verticalTraversal(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    queue := []*TreeWithDistance{{node: root, hd: 0, level: 0}}
    hash := map[int][]*TreeWithDistance{}
    min := math.MaxInt32
    max := math.MinInt32
    level := 0
    for len(queue) != 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            tmp := queue[i]
            hd := tmp.hd
            node := tmp.node
            hash[hd] = append(hash[hd], tmp)
            if node.Left != nil {
                queue = append(queue, &TreeWithDistance{
                    node:  node.Left,
                    hd:    hd - 1,
                    level: level,
                })
            }
            if node.Right != nil {
                queue = append(queue, &TreeWithDistance{
                    node:  node.Right,
                    hd:    hd + 1,
                    level: level,
                })
            }
            if min > hd {
                min = hd
            }
            if max < hd {
                max = hd
            }
        }
        queue = queue[size:]
        level++
    }
    result := [][]int{}
    for i := min; i <= max; i++ {
        if val, ok := hash[i]; ok {
            sort.Slice(val, func(i, j int) bool {
                if val[i].hd < val[j].hd {
                    return true
                }
                if val[i].hd > val[j].hd {
                    return false
                }
                if val[i].level < val[j].level {
                    return true
                }
                if val[i].level > val[j].level {
                    return false
                }
                return val[i].node.Val < val[j].node.Val
            })
            tmpResult := []int{}
            for _, n := range val {
                tmpResult = append(tmpResult, n.node.Val)
            }
            result = append(result, tmpResult)
        }
    }
    return result
}