常见二叉树面试题：深度优先遍历（DFS）

jjw0160

面试中，谈到二叉树大家是不是容易紧张，各种红黑树、平衡树、大小堆，不要紧张。今天就开始逐个破解，首先来讲二叉树的深度优先遍历（DFS：Depth First Search）相关知识。

二叉树

深度优先遍历，指的是遍历一颗二叉树时，先尽可能的走到最深一层的节点，然后再考虑广度。如上图，先根序（）DFS）遍历的顺序应为：
A-B-D-E-C-F-G
这种深度优先搜索的代码实现其实非常简单，一般借助递归的思想，将当前节点值输出，然后递归左子树，再递归右子树。
废话不多说，看代码：
// 声明数据结构
class Node{
Node left;
Node right;
String value;

public Node(String value) {
this.value = value;
}
}

public class DFS {
public static void main(String[] args) {
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");
Node f = new Node("F");
Node g = new Node("G");

a.left=b;
a.right=c;

b.left = d;
b.right = e;

c.left = f;
c.right = g;

dfs(a);
}

public static void dfs(Node root) {
System.out.println(root.value); // 输出相应内容，或做些其他操作。
if (root.left != null) {
dfs(root.left);
}
if (root.right != null) {
dfs(root.right);
}
}
}

/* 输出为：
D
E
B
F
G
C
A
*/
而中根序只需将输出代码移动到遍历左子树之后，此时输出顺序应为：“D-B-E-A-F-C-G”
/**
* 中根序遍历
* @param root
*/
public static void dfs(Node root) {
if (root.left != null) {
dfs(root.left);
}
System.out.println(root.value); // 在遍历左子树之后进行输出。
if (root.right != null) {
dfs(root.right);
}
}后根序，则将输出代码放置到遍历右子树后即可，此时输出顺序为：“D-E-B-F-G-C-A”
/**
* 后根序遍历
* @param root
*/
public static void dfs(Node root) {
if (root.left != null) {
dfs(root.left);
}
if (root.right != null) {
dfs(root.right);
}
System.out.println(root.value); // 在遍历右子树之后进行输出。
}最后，欢迎大家关注、转发。

heaven傲视天下

转发了

hujunnan5

转发了