LeetCode.314。二分木垂直順序走査

Leetcode 314 Binary Tree Vertical Order Traversal

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

この質問により、ツリーを垂直にトラバースできます。これは、レイヤートラバーサルと非常によく似ています。初めてそれをしたとき、再帰形式を使用しましたが、順序が間違っていることがわかりました。
したがって、レイヤーごとのトラバーサルを使用して、ツリーをレイヤーごとにキューに追加し、処理のために取り出す必要があります。

トラバースする場合、左ノードの場合は-1、右ノードの場合は+1であるため、左から右への階層順序が記憶されます。

2つのリストを使用して、それぞれ正の数とゼロのリスト、および負の数のリストを格納しています。

class Solution { public static class Pair { public int level = 0 public TreeNode treeNode public Pair(int l, TreeNode tn) { level = l treeNode = tn } } public List<List<Integer>> verticalOrder(TreeNode root) { List<List<Integer>> positive = new ArrayList<>() List<List<Integer>> negative = new ArrayList<>() if (root == null) { return positive } Queue<Pair> queue = new ArrayDeque<>() queue.add(new Pair(0, root)) while (!queue.isEmpty()) { int size = queue.size() List<Integer> temp = new ArrayList<>() for (int i = 0 i < size i++) { Pair pair = queue.poll() if (pair.level >= 0) { if (positive.size() <= pair.level) { positive.add(new ArrayList<>()) } positive.get(pair.level).add(pair.treeNode.val) } else { int index = Math.abs(pair.level) - 1 if (negative.size() <= index) { negative.add(new ArrayList<>()) } negative.get(index).add(pair.treeNode.val) } temp.add(pair.treeNode.val) if (pair.treeNode.left != null) { queue.add(new Pair(pair.level - 1, pair.treeNode.left)) } if (pair.treeNode.right != null) { queue.add(new Pair(pair.level + 1, pair.treeNode.right)) } } } for (List<Integer> list : negative) { positive.add(0, list) } return positive } }