一定要早日上岸鸭 · July 31, 2021 0

987. 二叉树的垂序遍历

987. 二叉树的垂序遍历

这道题可以用哈希表来存储整个二叉树, 哈希表为 key: TreeNode, value: (row, col, val) 在之后用sort来sort这个list,之后用双指针来保证相同列的为一组.

/** * 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; } }

也可以用优先队列来维护排序

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); } } }