标书制作公司网站,做网站会什么,免费看今天开始做女神的网站,昆明网站建设猫咪科技题目描述
给你二叉树的根结点 root #xff0c;请你设计算法计算二叉树的 垂序遍历 序列。
对位于 (row, col) 的每个结点而言#xff0c;其左右子结点分别位于 (row 1, col - 1) 和 (row 1, col 1) 。树的根结点位于 (0, 0) 。
二叉树的 垂序遍历 从最左边的列开始直到…题目描述
给你二叉树的根结点 root 请你设计算法计算二叉树的 垂序遍历 序列。
对位于 (row, col) 的每个结点而言其左右子结点分别位于 (row 1, col - 1) 和 (row 1, col 1) 。树的根结点位于 (0, 0) 。
二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束按列索引每一列上的所有结点形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点则按结点的值从小到大进行排序。
返回二叉树的 垂序遍历 序列。
示例 1 输入root [3,9,20,null,null,15,7]
输出[[9],[3,15],[20],[7]]
解释
列 -1 只有结点 9 在此列中。
列 0 只有结点 3 和 15 在此列中按从上到下顺序。
列 1 只有结点 20 在此列中。
列 2 只有结点 7 在此列中。
示例 2 输入root [1,2,3,4,5,6,7]
输出[[4],[2],[1,5,6],[3],[7]]
解释
列 -2 只有结点 4 在此列中。
列 -1 只有结点 2 在此列中。
列 0 结点 1 、5 和 6 都在此列中。1 在上面所以它出现在前面。5 和 6 位置都是 (2, 0) 所以按值从小到大排序5 在 6 的前面。
列 1 只有结点 3 在此列中。
列 2 只有结点 7 在此列中。
987. 二叉树的垂序遍历
解题思路
首先本题是一道困难题其解决方法并不难想主要难度主要集中在实现的细节。对于相同列的排序行小的在前同行的按照从大到小排序所以这个实现我想到了java的排序器制定类的规则。这个问题想好就按照dfs进行一次遍历主要记录行列将同列的放入同一个List从而进行排序整体实现思路并不复杂主要需要看清楚题意并认真实现。
具体实现代码如下
class Solution {public ListListInteger verticalTraversal(TreeNode root) {MapInteger, ListNode map new HashMap();ListListInteger lists new ArrayList();ListInteger list new ArrayList();dfs(0, 0, root, map, list);Collections.sort(list);//进行排序for (int i : list) {Collections.sort(map.get(i));ListInteger l new ArrayList();for (Node n : map.get(i))l.add(n.val);lists.add(l);}return lists;}public void dfs(int c, int r, TreeNode p, MapInteger, ListNode map, ListInteger list) {if (p ! null) {if (!map.containsKey(c)) {list.add(c);map.put(c, new ArrayListNode());}map.get(c).add(new Node(r, p.val));dfs(c - 1, r 1, p.left, map, list);dfs(c 1, r 1, p.right, map, list);}}
}class Node implements ComparableNode {int r;int val;Node(int r, int val) {this.r r;this.val val;}public int compareTo(Node o) {//排序器if (this.r o.r) {return 1;} else if (this.r o.r) {return -1;} else {if (this.val o.val)return 1;else if (this.val o.val)return -1;elsereturn 0;}}
}
