LC: 314. Binary Tree Vertical Order Traversal
https://leetcode.com/problems/binary-tree-vertical-order-traversal/
314. Binary Tree Vertical Order Traversal
Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]Example 2:
Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]Example 3:
Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]Example 4:
Input: root = []
Output: []Constraints:
The number of nodes in the tree is in the range
[0, 100].-100 <= Node.val <= 100
Binary Tree Vertical Order Traversal
The Essence:
Es sei ein Elterknoten in der Spalte C. Dann befindet sich sein linkes Kind in der Spalte C-1 und sein rechtes Kind C+1. Jeder Knotenwert in der Spalte muss auch "zeilensortiert" sein, d. h. von der Wurzel des Baumes bis zu den Blättern. Wenn die Wurzel als Pivot-Spalte angenommen wird, können alle anderen Knoten in Bezug auf diesen in ihren Spalten gestellt werden.
Details:
Es gibt etliche Methoden und Datenstrukturen, wodurch dieses Problem zu lösen ist. Viele wenden Traversierungsmethode wie Tiefensuche und Breitensuche sowie Datenstrukturen wie Hashtabellen an
Solution(s) and Further Explanation: The implementations and their explanations can be found here:
Default Code:
Last updated