树的遍历

深度优先遍历

树的基本操作,肯定要熟练掌握的。以下的三种遍历,其实就是通过中间的树的值什么时候遍历来命名的。左子树永远优先右子树遍历。而且以下三种遍历都是属于深度优先遍历(Depth First Search),但是一般都是用的先序遍历。

inorder输出

就是中序遍历:

  • 先遍历左边的
  • 然后遍历中间的
  • 最后遍历右边的子树

python实现:

1
2
3
4
5
def helper(self, root, res):
if root:
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)

java实现:

1
2
3
4
5
6
7
private void inOrder(TreeNode root) {
if (root != null) {
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}

preorder输出

先序遍历:

  • 先遍历根
  • 再遍历左子树
  • 最后遍历右子树

python实现:

1
2
3
4
5
def helper(self, root, res):
if root:
res.append(root.val)
self.helper(root.left, res)
self.helper(root.right, res)

java实现:

1
2
3
4
5
6
7
private void preOrder(TreeNode root) {
if (root != null) {
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
}

postorder输出

后序遍历:

  • 先遍历左子树
  • 在遍历右子树
  • 最后遍历根

python实现

1
2
3
4
5
6
7
8
def helper(self, root, res):
if not root:
return
if root.left:
self.helper(root.left, res)
if root.right:
self.helper(root.right, res)
res.append(root.val)

java实现:

1
2
3
4
5
6
7
8
9
10
11
12
private void postOrder(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
postOrder(root.left);
}
if (root.right != null) {
postOrder(root.right);
}
System.out.print(root.val + " ");
}

使用栈实现先序遍历

当然可以使用数据结构来实现,省点空间,但是我感觉还是递归更容易阅读。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void preOrderInStack(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode tmp = root;
while (tmp != null || !stack.isEmpty()) {
if (tmp != null) {
System.out.print(tmp.val + " ");
stack.push(tmp);
tmp = tmp.left;
} else {
// 左子树已经完毕
tmp = stack.pop().right;
}
}
}

广度优先遍历

一般来说广度优先就只有一种遍历(因为左边的永远优先于右边的),利用队列很简单就实现了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void bfs() {
Deque<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int length = queue.size();
for (int i = 0; i < length; i++) {
TreeNode tmp = queue.getFirst();
queue.removeFirst();
System.out.print(tmp.val + " ");
if (tmp.left != null) {
queue.add(tmp.left);
}
if (tmp.right != null) {
queue.add(tmp.right);
}
}
}
}