正文之前
闲得无聊去刷 LeetCode 的时候做了一点深搜和广搜的题，但是树的遍历方式还没有写过总结，今天刚好总结一下：
- 深度优先搜索
- 前序遍历
- 中序遍历
- 后序遍历
- 广度优先搜索
正文
1. 节点的定义
这里定义树的节点的方式就按照 LeetCode 上给出的吧：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
接下来给出用例：
TreeNode node10 = new TreeNode(10);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
TreeNode node1 = new TreeNode(1);
TreeNode node3 = new TreeNode(3);
TreeNode node0 = new TreeNode(0);
TreeNode node2 = new TreeNode(2);
TreeNode node4 = new TreeNode(4);
TreeNode node6 = new TreeNode(6);
node10.left = node7;
node10.right = node8;
node7.left = node1;
node7.right = node3;
node3.left = node0;
node3.right = node2;
node8.left = node4;
node8.right = node6;
在遍历时用 ArrayList 来存放根节点的值，
2. 深度优先搜索
分别有三种方式，前序先访问根节点，中序第二个访问根节点，后序最后访问根节点，这里写给出三种方法，然后统一测试一下：
//前序遍历
public void preOrderTraversal(TreeNode node, ArrayList<Integer> list){
if (node == null){
return;
}
//先访问根节点
list.add(node.val);
//然后是左子节点和右子节点
preOrderTraversal(node.left, list);
preOrderTraversal(node.right, list);
}
//中序遍历
public void inOrderTraversal(TreeNode node, ArrayList<Integer> list){
if (node == null){
return;
}
//先访问左子节点，然后是根节点，最后是右子节点
inOrderTraversal(node.left, list);
list.add(node.val);
inOrderTraversal(node.right, list);
}
//后序遍历
public void postOrderTraversal(TreeNode node, ArrayList<Integer> list){
if (node == null){
return;
}
postOrderTraversal(node.left, list);
postOrderTraversal(node.right, list);
list.add(node.val);
}
根据我们定义的用例，三种遍历方式的输出分别是这样的：
ArrayList<Integer> list = new ArrayList<>();
System.out.print("前序遍历：");
s.preOrderTraversal(node10, list);
for (Integer i: list) {
System.out.print(i + " ");
}
list.clear();
System.out.println();
System.out.print("中序遍历：");
s.inOrderTraversal(node10, list);
for (Integer i: list) {
System.out.print(i + " ");
}
list.clear();
System.out.println();
System.out.print("后序遍历：");
s.postOrderTraversal(node10, list);
for (Integer i: list) {
System.out.print(i + " ");
}
得到输出：
前序遍历：10 7 1 3 0 2 8 4 6
中序遍历：1 7 0 3 2 10 4 8 6
后序遍历：1 0 2 3 7 4 6 8 10
3. 广度优先搜索
广搜的方式就是一层一层的访问节点，又叫做层次遍历，用队列来实现：
public void BFS(TreeNode node, ArrayList<Integer> list){
Queue<TreeNode> queue = new LinkedList<>();
if (node != null){
//根节点作为第一层，先加入
queue.add(node);
while (!queue.isEmpty()){
TreeNode cur = queue.poll();
list.add(cur.val);
//依次加入左右子节点
if (cur.left != null){
queue.offer(cur.left);
}
if (cur.right != null){
queue.offer(cur.right);
}
}
}
}
遍历的结果是：
层次遍历：10 7 8 1 3 4 6 0 2
我用图来走一遍流程：
每次出队列一个节点，然后把它的子节点（如果存在）加入到队列，循环往复，直到队列为空
4. LeetCode 水题
既然介绍了树的遍历，就随便拿两个简单的题来做个例子吧：
求二叉树的所有路径，这一题可能和遍历有一点区别（因为是路径，根节点会出现多次），不过想法是一样的，用的前序，先访问根节点，然后是左右子节点：
public List<String> binaryTreePaths(TreeNode root) {
String s = "";
List<String> list = new ArrayList<>();
if (root != null){
DFS(s, root, list);
}
return list;
}
public void DFS(String s, TreeNode node, List<String> list){
if (node.left == null && node.right == null){
list.add(s + node.val);
}
if (node.left != null){
DFS(s + node.val + "->", node.left, list);
}
if (node.right != null){
DFS(s + node.val + "->", node.right, list);
}
}
513. Find Bottom Left Tree Value
求二叉树最底层的最左边节点，用的层次遍历，只不过这次是从右往左，最后一个出队列的就是目标节点了：
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
root = queue.poll();
if (root.right != null){
queue.add(root.right);
}if (root.left != null){
queue.add(root.left);
}
}
return root.val;
}
关于树的遍历就到这里了
