树的基础算法(一) -- 遍历
偶是曾小贤1213:
thks师兄，讲的非常清楚 ！[打call][打call]
不住在阿拉善:
“平衡二叉树必定是二叉搜索树”，感觉这个并不成立？
想看蔚蓝的大海:
想问一下987题的哪个题的排序是如何处理会比较好一些，视频里提到了但还不是很理解[笑哭]
【回复】应该有两种方式去做。
第一种是Map<Integer, PQ<int【】>> map的key是col, pq里面存row和val， 然后每次入Q的时候先比row, row一样在比val，剩下的和314基本一样。
第二种就是前面和314都一样， 但List里面不能是pure integer， 要存一个int【】, 然后每次往res里面加的时候都call一下Collections.sort 就可以了。
但第二种的复杂度有可能是O(wn log n), w是树的宽度， 因为有w个List， 每次sort是（n log n), 所以总复杂度会高一些， 但不是很确定。
【回复】314. Binary Tree Vertical Order Traversal
987. Vertical Order Traversal of a Binary Tree
两个题目同一个位置的node排序要求不一样
987 There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.
314 If two nodes are in the same row and column, the order should be from left to right.
advise2015:
古城， 我提供另外一种更好记的模板， 这种模板的好处是三种遍历都是一样的模板， 坏处是空间复杂度会稍高一点， 但还是O（n）
只需要记住我们想要的结果其实就是stack的pop order， 那么当我们入栈的时候就要用reverse order, 每次push到cur node的时候， 再push一个null进去就可以了。以下是java的代码
private void iter(TreeNode root, List<Integer> res) {
if (root == null) return;
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
// pop order: cur -> left -> right
// push order: right -> left -> cur
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
if (cur == null) {
cur = stack.pop();
res.add(cur.val);
} else {
if (cur.right != null)
stack.push(cur.right);
if (cur.left != null)
stack.push(cur.left);
stack.push(cur);
stack.push(null);
}
}
}
【回复】这是pre order的代码， 其他两种只需要更改push cur的位置即可
