Created
August 7, 2020 11:40
-
-
Save kuntalchandra/fda7c787677ccd8b289ab63d3a762ffd to your computer and use it in GitHub Desktop.
Vertical Order Traversal of a Binary Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
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). | |
Example 2: | |
Input: [1,2,3,4,5,6,7] | |
Output: [[4],[2],[1,5,6],[3],[7]] | |
Explanation: | |
The node with value 5 and the node with value 6 have the same position according to the given scheme. | |
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6. | |
Note: | |
The tree will have between 1 and 1000 nodes. | |
Each node's value will be between 0 and 1000 | |
Approach: | |
Respect: Beautifully explained here, found it intuitive than the official solution - | |
https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/discuss/231327/PYTHON-solution-with-explanation | |
> Root node is considered as 0 horizontal distance. | |
->As we move left hd is decreased by 1 and is increased by 1 as we move right. | |
->vd is used to get the top to bottom series. | |
->comparison in each dic is done based on vd value | |
-> if vd comes out to be same then node value is compared. | |
""" | |
from collections import defaultdict, deque | |
from typing import List | |
# Definition for a binary tree node. | |
class TreeNode: | |
def __init__(self, val=0, left=None, right=None): | |
self.val = val | |
self.left = left | |
self.right = right | |
class Solution: | |
def verticalTraversal(self, root: TreeNode) -> List[List[int]]: | |
if not root: | |
return [] | |
q = deque() | |
q.append([root, 0, 0]) | |
dic = defaultdict(list) | |
while q: | |
for _ in range(len(q)): | |
node, hd, vd = q.popleft() | |
dic[hd].append([vd, node.val]) | |
if node.left: | |
q.append([node.left, hd - 1, vd - 1]) | |
if node.right: | |
q.append([node.right, hd + 1, vd - 1]) | |
res = [] | |
for i in sorted(dic.keys()): | |
level = [x[1] for x in sorted(dic[i], key=lambda x: (-x[0], x[1]))] | |
res.append(level) | |
return res |
Author
kuntalchandra
commented
Aug 7, 2020
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment