987. 二叉树的垂序遍历
这道题可以用哈希表来存储整个二叉树, 哈希表为 key: TreeNode, value: (row, col, val) 在之后用sort来sort这个list,之后用双指针来保证相同列的为一组.
<![CDATA[
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public Map<TreeNode, int[]> hm = new HashMap<TreeNode, int[]>();
public void dfs(TreeNode root){
if(root == null) return;
int[] row_col_val = hm.get(root);
int row = row_col_val[0], col = row_col_val[1];
// System.out.println(row+" "+ col);
if(root.left!=null){
hm.put(root.left, new int[] {row+1, col-1, root.left.val});
dfs(root.left);
}
if(root.right!=null){
hm.put(root.right, new int[] {row+1, col+1, root.right.val});
dfs(root.right);
}
}
public List<List<Integer>> verticalTraversal(TreeNode root) {
hm.put(root, new int[] {0, 0, root.val});
dfs(root);
// System.out.println(hm.toString());
List<int[]> list = new ArrayList<>(hm.values());
Collections.sort(list, (a,b)->{
if(a[1]!=b[1]) return a[1]-b[1];
if(a[0]!=b[0]) return a[0]-b[0];
return a[2]-b[2];
});
int len = list.size();
List<List<Integer>> ret = new ArrayList<List<Integer>>();
for(int i=0; i<len;){
int j=i;
List<Integer> temp = new ArrayList<Integer>();
while(j<len && list.get(i)[1]==list.get(j)[1]) temp.add(list.get(j++)[2]);
i = j;
ret.add(temp);
}
// System.out.println(list.get(3)[2]);
return ret;
}
}
]]>
也可以用优先队列来维护排序
<![CDATA[
class Solution {
PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->{ // col, row, val
if (a[0] != b[0]) return a[0] - b[0];
if (a[1] != b[1]) return a[1] - b[1];
return a[2] - b[2];
});
public List<List<Integer>> verticalTraversal(TreeNode root) {
int[] info = new int[]{0, 0, root.val};
q.add(info);
dfs(root, info);
List<List<Integer>> ans = new ArrayList<>();
while (!q.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
int[] poll = q.peek();
while (!q.isEmpty() && q.peek()[0] == poll[0]) tmp.add(q.poll()[2]);
ans.add(tmp);
}
return ans;
}
void dfs(TreeNode root, int[] fa) {
if (root.left != null) {
int[] linfo = new int[]{fa[0] - 1, fa[1] + 1, root.left.val};
q.add(linfo);
dfs(root.left, linfo);
}
if (root.right != null) {
int[] rinfo = new int[]{fa[0] + 1, fa[1] + 1, root.right.val};
q.add(rinfo);
dfs(root.right, rinfo);
}
}
}
]]>
