树的基础算法(一) -- 遍历

Рет қаралды 8,945

Күн бұрын

Пікірлер: 39

@Grace0720mcy 2 жыл бұрын

城主我想提议可以加timestamp方便大家搜索例如： 14:58 前中后序遍历 recursive 16:16 Preorder iterative 18:34 Inorder iterative 20:24 Postorder iterative 24:33 Level Order 上而下 29:29 Level Order II 下而上 30:21 Zigzag Order 31:51 Vertical Order

@古城算法 2 жыл бұрын

太棒了，我把你这个加上拉~~

@woogieboogie9838 8 ай бұрын

30:21 Zigzag Order 古城老师 BFS 程式码第18行註解有小typo 是偶数由左往右 (0,2,4层正常显示) 第19行才是奇数由右往左感谢古城完美的演讲!

@古城算法 8 ай бұрын

感谢指出

@hz4353 2 жыл бұрын

宝藏频道，总结的很好受益匪浅

@lomoyang3034 3 жыл бұрын

同学的提问非常好，也是我这周做题目时想到的一个问题。

@古城算法 3 жыл бұрын

感谢支持~~

@wangrichard2140 3 жыл бұрын

非常好👍

@古城算法 3 жыл бұрын

感谢支持！！

@ExplosionBobXD 3 жыл бұрын

这么好的频道我都不舍得分享给别人

@古城算法 3 жыл бұрын

感谢支持！！

@elenawu6390 2 жыл бұрын

城主，在314 题。我试了在queue中存储pair(为了加上col的信息)，这样就可以直接在弹出的时候拿到col, 省去了position 这个hashmap.

@古城算法 2 жыл бұрын

非常棒！

@weibinsun5771 2 жыл бұрын

听到天利38套我绷不住了😂

@frederickbarbarossa2746 Жыл бұрын

44:34 既然同学提问要最后倒序何不直接res就是个stack 最后pop出来就倒叙了

@LorieLuo Жыл бұрын

你好，我想请问一下314的dfs解法对于node 3,0,1是怎么保证0和1的顺序的呢？题目要求如果same row and column需要从左往右，但是算法里面似乎没有体现？

@liang-v8n Жыл бұрын

stable sort

@youran1880 3 жыл бұрын

987应该不止是简单的把同一col的node sort一遍就可以了。987要求先输出row在上的，同一row同一col的才可以sort。所以在314example 2的那个图的情况下，3的col应该输出3，0，1。所以这道题需要再用一个rowtoNode的map在bfs每一层时把同一层同一col的node sort后再放进colmap

@古城算法 3 жыл бұрын

987同一位置是按照value大小排序吧。题目中有给条件说 There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

@古城算法 3 жыл бұрын

Collections.sort(ret, (a, b) -> (a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2])); 我们这里就比较了第二个位置value当行列相同的时候

@古城算法 3 жыл бұрын

感谢提醒，我在视频里可能漏说了这一点。

@古城算法 3 жыл бұрын

List ret = new ArrayList(); public List verticalTraversal(TreeNode root) { List res = new ArrayList(); check(root, 0, 0); Collections.sort(ret, (a, b) -> (a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2])); int preX = Integer.MIN_VALUE; for (int[] x : ret) { if (x[0] != preX) { preX = x[0]; res.add(new ArrayList()); } res.get(res.size() - 1).add(x[2]); } return res; } private void check(TreeNode node, int x, int y) { if (node == null) return; ret.add(new int[] {x, y, node.val}); check(node.left, x-1, y+1); // y+1, not y-1 here check(node.right, x+1, y+1); }