首页 > 代码库 > 314. Binary Tree Vertical Order Traversal

314. Binary Tree Vertical Order Traversal

2024-08-17 00:14:47   217人阅读

这个题不难，但是挺有趣的。

1.就是在每个递归的时候，传一个index进去，如果根节点是0，那么左子树就是-1，右子树就是1。

左子树的左子树就是-1，左子树的右子树就是0，etc

 

2.然后这道题还有一个坑，就是要level order，所以必须bfs，如果dfs递归的话，相同的index的节点输出的顺序可能就会反了。

 

3.其实这道题是我上个月刷的时候做的，但是今天重新做了发现没有写过。之前的做法是正反两个map，node2index+index2node，这样正反存，但是感觉写起来比较丑。

我这次写的时候把index+TreeNode打包成一个新的类，这样只用当做普通的node来处理就行了。

 

4.还有要说的一个点就是，因为map里面的index是没有顺序的，我们最后结果要按照index顺序输出，所以可以在遍历的时候就维持一个index的最小值和最大值。

 

 1     class Node {
 2         int index;
 3         TreeNode root;
 4         public Node(int index, TreeNode root) {
 5             this.index = index;
 6             this.root = root;
 7         }
 8     }
 9     
10     public List<List<Integer>> verticalOrder(TreeNode root) {
11         List<List<Integer>> res = new ArrayList<>();
12         if(root == null) {
13             return res;
14         }
15         int[] minMax = new int[2];
16         minMax[0] = Integer.MAX_VALUE;
17         minMax[1] = Integer.MIN_VALUE;
18         Map<Integer, List<Integer>> map = new HashMap<>();
19         Queue<Node> queue = new LinkedList<>();
20         Node nodeRoot = new Node(0, root);
21         queue.offer(nodeRoot);
22         while(!queue.isEmpty()) {
23             Node cur = queue.poll();
24             List<Integer> list = map.get(cur.index);
25             if(list == null) {
26                 list = new ArrayList<Integer>();
27             }
28             list.add(cur.root.val);
29             map.put(cur.index, list);
30             minMax[0] = Math.min(minMax[0], cur.index);
31             minMax[1] = Math.max(minMax[1], cur.index);
32             if(cur.root.left != null) {
33                 Node left = new Node(cur.index - 1, cur.root.left);
34                 queue.offer(left);
35             }
36             if(cur.root.right != null) {
37                 Node right = new Node(cur.index + 1, cur.root.right);
38                 queue.offer(right);
39             }
40         }
41         for(int i = minMax[0]; i <= minMax[1]; i++) {
42             res.add(map.get(i));
43         }
44         return res;
45     }

 

314. Binary Tree Vertical Order Traversal


联系
我们