如何解决LeetCode上的二叉树问题？

本文共计14215个文字，预计阅读时间需要57分钟。

专题：二叉树遍历87.

二叉树的遍历算法设计

给你二叉树的根节点 root，请设计算法计算二叉树的层序遍历和前序遍历。

对于位于 (row, col) 的每个节点，请按照以下规则输出：

- 层序遍历：从上到下，从左到右。- 前序遍历：根节点 -> 左子树 -> 右子树。

例如，对于二叉树：

1 / \ 2 3 / \ \

45 6

层序遍历为：[1, 2, 3, 4, 5, 6]前序遍历为：[1, 2, 4, 5, 3, 6]

专题：二叉树遍历 987. 二叉树的垂序遍历

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

一、解题思路

​ 上图中标出的坐标中，前为行号，后为列号，本题实质上就是排序。本题排序规则为：列号从小到大；对于同列结点，按照行号从小到大；对于同行同列结点，按数值从小到大。

​ 因此对该树遍历一遍，遍历同时记录每个节点的（col, row, value），遍历完成后，按照col为第一关键字升序，row为第二关键字升序，value为第三关键字升序，对所有结点进行排序。