The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
Solutions
Solution 1: DFS
DFS traverses the binary tree, recording the value, depth, and horizontal offset of each node. Then sort all nodes by horizontal offset from small to large, then by depth from small to large, and finally group by horizontal offset.
The time complexity is $O(n\log \log n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 910111213141516171819202122
# 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 = rightclassSolution:defverticalOrder(self,root:Optional[TreeNode])->List[List[int]]:defdfs(root,depth,offset):ifrootisNone:returnd[offset].append((depth,root.val))dfs(root.left,depth+1,offset-1)dfs(root.right,depth+1,offset+1)d=defaultdict(list)dfs(root,0,0)ans=[]for_,vinsorted(d.items()):v.sort(key=lambdax:x[0])ans.append([x[1]forxinv])returnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcverticalOrder(root*TreeNode)[][]int{d:=map[int][][]int{}vardfsfunc(*TreeNode,int,int)dfs=func(root*TreeNode,depth,offsetint){ifroot==nil{return}d[offset]=append(d[offset],[]int{depth,root.Val})dfs(root.Left,depth+1,offset-1)dfs(root.Right,depth+1,offset+1)}dfs(root,0,0)idx:=[]int{}fori:=ranged{idx=append(idx,i)}sort.Ints(idx)ans:=[][]int{}for_,i:=rangeidx{v:=d[i]sort.SliceStable(v,func(i,jint)bool{returnv[i][0]<v[j][0]})t:=[]int{}for_,x:=rangev{t=append(t,x[1])}ans=append(ans,t)}returnans}
Solution 2: BFS
A better approach to this problem should be BFS, traversing from top to bottom level by level.
The time complexity is $O(n\log n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 9101112131415161718192021
# 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 = rightclassSolution:defverticalOrder(self,root:Optional[TreeNode])->List[List[int]]:ifrootisNone:return[]q=deque([(root,0)])d=defaultdict(list)whileq:for_inrange(len(q)):root,offset=q.popleft()d[offset].append(root.val)ifroot.left:q.append((root.left,offset-1))ifroot.right:q.append((root.right,offset+1))return[vfor_,vinsorted(d.items())]
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcverticalOrder(root*TreeNode)[][]int{ans:=[][]int{}ifroot==nil{returnans}d:=map[int][]int{}q:=[]pair{pair{root,0}}forlen(q)>0{forn:=len(q);n>0;n--{p:=q[0]q=q[1:]root=p.nodeoffset:=p.offsetd[offset]=append(d[offset],root.Val)ifroot.Left!=nil{q=append(q,pair{root.Left,offset-1})}ifroot.Right!=nil{q=append(q,pair{root.Right,offset+1})}}}idx:=[]int{}fori:=ranged{idx=append(idx,i)}sort.Ints(idx)for_,i:=rangeidx{ans=append(ans,d[i])}returnans}typepairstruct{node*TreeNodeoffsetint}